First Unique Character in a String

Easy
0/40
Average time to solve is 15m
61 upvotes
Asked in companies
MicrosoftIBMLivekeeping (An IndiaMART Company)

Problem statement

Given a string ‘STR’ consisting of lower case English letters, the task is to find the first non-repeating character in the string and return it. If it doesn’t exist, return ‘#’.

For example:

For the input string 'abcab', the first non-repeating character is ‘c’. As depicted the character ‘a’ repeats at index 3 and character ‘b’ repeats at index 4. Hence we return the character ‘c’ present at index 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The only line of each test case contains a single string ‘STR’ consisting of only lowercase English letters.
Output Format: 
For each test case, print a single character representing the first non-repeating character in the given string.

The output for each test case is in a separate line.
Note: 
You do not need to print anything; it has already been taken care of.
Constraints: 
1 <= T <= 100
1 <= N <= 10 ^ 4

Where ‘T’ is the number of test cases, and ‘N’ is the length of the string.

Time Limit: 1 sec
Sample Input 1:
2
bbabcbcb
babaabea
Sample Output 1:
a
e
Explanation of Sample Input 1:
For the first test case, 
the first non-repeating character is ‘a’. As depicted the character ‘b’ repeats at index 1, 3, 5, 7, and character ‘c’ repeats at index 6. Hence we return the character ‘a’ present at index 2.

For the second test case, 
the character ‘e’ is the first non-repeating character. As depicted the character ‘b’ repeats at index 2, 5, and character ‘a’ repeats at index 3, 4, and 7. Hence we return the character ‘e’ present at index 6.
Sample Input 2:
3
cbbd
bebeeed
abcd
Sample Output 2:
c
d
a
Hint

Find the frequency of all characters in the string and check which character has a unit frequency.

Approaches (2)
Count array and two string traversals

A character is said to be non-repeating if its frequency in the string is equal to 1. To find such characters, one needs to find the frequency of all characters in the string and check which character has a unit frequency. This task could be done efficiently using an array to map the character to their respective frequencies. We can simultaneously update the frequency of any character we come across in constant time. The maximum number of distinct characters in the ASCII system is 256. So the array has a maximum size of 256. Now read the string again, and the first character we find has a frequency as unity is the answer.

 

Below is the algorithm:

 

  1. Create an array that will map the character to their respective frequencies.
  2. Traverse the given string.
  3. Increase the count of the current character in the array.
  4. Now traverse the string again and check whether the current character has a frequency equal to 1.
  5. If the frequency is more than 1, continue the traversal.
  6. Else break the loop and update the answer.
  7. In the end, return the first unique character in the string.
Time Complexity

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

 

Since, we are traversing the string to store and count the frequencies of the characters, which takes O(N) time. Thus, the overall time complexity is O(N).

Space Complexity

O(1).

 

Since no extra memory is used except a count array of constant size 256.

Code Solution
(100% EXP penalty)
First Unique Character in a String
Full screen
Console