First unique character in a string

Moderate

0/80

Average time to solve is 15m

8 upvotes

Asked in companies

Problem statement

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”.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
16
codingninjascode
24
practicepracticepractice

Sample Output 1:

6
-1

Explanation for Input 1:

For the first subtask the explanation is given in the problem statement. 

For the second subtask there are no unique characters so ans is -1.

Sample Input 2 :

3
19
palindromemordnilap
9
notunique
7
caaabbc

Sample Output 2:

10
2
-1

Explanation for Input 2:

For the first subtask, every character except ‘e’ occurs 2 times so we print the index of e that is 10. 

For the second subtask, the characters ‘o’ , ‘t’ , ‘e’ , ‘i’ and ‘q’ are unique but ‘o’ occurs before all the other unique characters .

For the third subtask, all the characters are not unique so we return -1.

Hint 1

Hint 2

Think of brute force.

Think whether the character at each index is unique or not.

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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).

Space Complexity

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

(100% EXP penalty)

First unique character in a string

Console