First Unique Character in a String
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

Question

First Unique Character in a String

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

Accepted Answer

Approach :
1) Make a count array and initialize all characters by -1, i.e., all considered as absent.
2) Traverse the given string, and the value of count[x] will be the index of ‘x’ if ‘x’ appears only once. Else, the value is going to be either -1 or -2.
3) Now, traverse the count array and check if the ith character occurs only once (count[i] has a positive value) and appears before the current result, then update the result.
4) Add the character present at the result index in the arraylist.

Accepted Answer

Bruteforce

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.

Space Complexity: O(1)Explanation:

O(1), as we are using constant extra memory.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the string.

As we are traversing the string for each index and there are N indices so the total complexity is O(N^2).

Accepted Answer

Using Hashmap

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.

Space Complexity: O(1)Explanation:

O(1), as there are at max 26 different characters so the size of hash map will not count.

Time Complexity: O(n)Explanation:

O( N ), where N is the length of the string S.

As we are traversing the string only once, that is O( N ) operations and after that checking the minimum index requires only 26 operations so the overall complexity is O ( N ).

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

Input format :

Output Format :

Note:

Constraint :

Top Amdocs Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amdocs Software Developer