Last Updated: 21 Dec, 2020
First unique character in a string
Moderate
Asked in companies
You are given a string S of length N. Your task is to find the index(considering 1-based indexing) of the first unique character present in the string. If there are no unique characters return -1.
Note
A unique character in a string is the character that appears only once in the string. For example, ‘h’, ‘e’, and ‘o’ are the unique characters in the string “hello”.
Input format :
The first line of input contains a single integer T, denoting the number of test cases.
The first line of each test case contains a positive integer N, which represents the length of the string.
The next line of each test case contains a string S.
Output Format :
For each test case, return the index of the first unique character, and if there is no unique character return “-1”.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraint :
1 <= T <= 100
1 <= N <= 10^4
Time Limit: 1 sec
Approaches
- Traverse through all the indices one by one and we will try to see if the character at the current index is unique or not.
- For this, if we are at index i, we will traverse through all the indices except i let say it j.
- Now if there are no characters equal to the ith character we will return it. Means if there is no j subject to constraint that j != i such that S[ i ] = S[ j ], then we will return i.
- We are stopping for the first time we are getting something unique so it will always be the first unique character.
- If there are no unique characters we will return -1.
- For this approach, we have to use a hash map. We can also use an array to store frequency as the given string contains only lowercase letters so we can map each letter to its position in alphabetical order for example position of ‘a’ will be 1, ‘b’ will be 2 and so on.
- Traverse the string S and store the frequency of all the elements in a hash map.
- Now again traverse the S and see if the current character has frequency 1, if yes then return the index.
- The above method gives us the optimal answer but it uses 2 traversals of the string so let us try to optimise it to one traversal.
- For this, we will use another array to store the first occurrence of a character.
- Now in the first traversal along with the hash map, we will also store the first occurrence of a character.
- After this we will traverse through all the characters and from all the unique characters that are having frequency 1 we will find the one which has minimum index i.e. the first unique character and we will return it.
- Let us take an example to understand it , let S be “codingninjascode” we will traverse it and calculate frequency and occurrence. We will get the following values.
- HASH_MAP[c] = 2 , OCCURENCE[c] = 1
- HASH_MAP[o] = 2 , OCCURENCE[o] = 2
- HASH_MAP[d] = 2 , OCCURENCE[d] = 3
- HASH_MAP[i] = 2 , OCCURENCE[c] = 4
- HASH_MAP[n] = 3 , OCCURENCE[c] = 5
- HASH_MAP[g] = 1 , OCCURENCE[c] = 6
- HASH_MAP[j] = 1 , OCCURENCE[c] = 10
- HASH_MAP[a] = 1 , OCCURENCE[c] = 11
- HASH_MAP[s] = 1 , OCCURENCE[c] = 12
- HASH_MAP[e] = 1 , OCCURENCE[c] = 16
- So among all the characters with frequency 1 , i.e. the minimum occurrence is of character ‘g’ that is 6.