You are most likely to encounter string questions in your upcoming tech giant’s coding interview!
From longest palindromic substring to superstring to palindrome partitioning, you will be asked a variety of string related coding questions.
One such important string topic that often appears in the coding interviews is finding the first unique characters in a string.
Here, you will be given a string and you need to find all the non-repeating characters in that string. For that, you may need to follow certain approaches in order to find the unique characters in the string.
Without any ado, let’s get started!
First unique characters in a string
In order to find the first unique character in a string, you need to consider the frequency of all its characters. For that, you can consider the desired problem statement.
Problem Statement
A string as ‘s’ is given. Your task would be to find its first unique character that will not be repeated in the given string of all characters while returning the index as an output. Though, if there will not be any such character, you will return -1 as the desired output.
If the input is s = tutorialspoint
The output would be 1.
In this string, ‘tutorialspoint’, its first unique character would not be repeated as the u with that of index as 1. You will return the output as 1.
Approaches to follow
When you talk about finding the first unique characters in a string, you need to follow certain approaches in order to get all the unique characters present in a given string.
Hashmap approach
The first approach for finding all unique characters in a given string would be the hashmap approach. In this method, you will find all the first unique characters that will be present in the given string.
The idea behind this approach would be to get all the characters in a given string while creating the required hashmap with the key as the characters or the value of occurrences.
When traversing through each of the characters in a given string, you can store the occurrences of all the characters as and when it appears. It may take the O[n] linear time so as to store all occurrences of each character.
Then, you can go back towards the hashmap in order to check if there are any characters present with that of the frequency that is less than 2 or can be equal to the 1. With this you can easily return the given index of each character.
- Take the given string ‘s’ as the required input
- There will be an integer function with the uniqueChar whose string will be taken as the input in order to return the index for the first appearing unique characters
- You can iterate over that string in order to create the hashmap of the char with its occurrences while you go through the characters of that particular string
- If there will be the characters with frequency which is less than that of 2 or equal to the 1 which then return an index of a particular character
- If there will not be any unique characters which would be present in the given string , then return -1 as the output
Using hashmap and single traversal
The idea behind this approach would be to count the number of arrays despite using a hash_map for the maximum number of characters. You can augment your count arrays in order to store not just its count but also the required index of its first characters.
When it comes to getting the first non-repeating characters, you have to scan a count array instead of using the strings.
Follow the below-mentioned steps for solving the problem:
- Make a given count_array with the help of two fields which are frequency or the first occurrence of a given character
- Note down the size of a given count_array
- You can traverse the given string with the help of a pointer
- Then increase the count of all current characters in order to update the occurrences
- Now, the array would contain all valid first occurrences of the characters with the given frequency as the unity.
- You can traverse the count_array[] in such a way to find all the characters with that of the occurrence value with the frequency value as the given unity
- Then, return all the characters
As all the strings will be needed to traverse at least one time, the time complexity in this case would be the O[n]
Using the string function find()
With the help of find() function, you can get the first unique characters in the string. The idea in this case would be to search the required current character in that string after its first occurrence. Though, if the character will be found with that of the remaining string, you can reverse it.
The search in this case will be done with the help of the in-built find() function. For every first unique character the output would be f.
Using the naive approach
The idea behind this approach is to loop over a given string for all the characters in order to check if there is the occurrence of all the same characters in a given string.
If the occurrence count in this case is 1, you can return the character or else, you can search for all the characters in a given string. You can count for occurrence 1 in order to return the character. Or else, search for its remaining characters.
Traverse all the strings for each of the characters with that of size n to get the required time complexity.
Wrapping Up
Take into account all the essential string concepts like first unique characters in a string, longest palindromic string alongside other concepts like palindrome partitioning, arrays concepts among others.
Get better insights on finding the unique characters of a string with this blog post and fill your knowledge gap.