First Unique Character In A String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
29 upvotes
Asked in companies
OYOAmdocs

Problem statement

You are given a string A consisting of lower case English letters. You have to find the first non-repeating character from each stream of characters.

For Example: If the given string is 'bbaca', then the operations are done as:

The first stream is “b” and the first non-repeating character is ‘b’ itself, so print ‘b’. 
The next stream is “bb” and there are no non-repeating characters, so print nothing.
The next stream is “bba” and the first non-repeating character is ‘a’, so print ‘a’. 
The next stream is “bbac” and the first non-repeating character is ‘a’, so print ‘a’. 
The next stream is “bbaca” and the first non-repeating character is ‘c’, so print ‘c’.
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 A consisting of only lowercase English letters.
Output Format: 
For each test case, print a single character representing the first non-repeating character for each stream of characters.

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 <= 10000

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

Time Limit: 1 sec.
Sample Input 1:
2
bbabcbcab
bab
Sample Output 1:
b a a a a a
b b a
Explanation of Sample Input 1:
For the first test case, the first stream is “b” and the first non-repeating character is ‘b’ itself, so add ‘b’ in the arraylist. For the second stream of characters, i.e., after reading character ‘b’ from the stream, the string becomes “bb”, for which all the characters are repeating, so no need to add in the arraylist. For the third stream of characters, “bba”, the first non-repeating character is ‘a’, so add ‘a’ in the arraylist. In this way, the first non-repeating character is added to the arraylist for each stream of characters.

For the second test case, ‘b’ is the first non-repeating character for the first stream, “b”. For the stream “ba”, the first non-repeating character so far ‘b’. For the stream “bab”, the first non-repeating character so far is ‘a’. So, the final arraylist will be [b, a, a].
Sample Input 2:
3
cbbd
bebeeed
abcd
Sample Output 2:
c c c c
b b e d
a a a a
Hint

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

Approaches (3)
Count array and two string traversals

A character is said to be non-repeating if its frequency in the string is unit. 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 a count 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 distinct characters in the ASCII system are 256. So the count 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. Make a count 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 count array.
  4. Now traverse the string again and check whether the current character has frequency=1.
  5. If the frequency>1, continue the traversal.
  6. Else break the loop and add the current character in the arraylist.
Time Complexity

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

 

Since for each of the ‘N’ streams of characters, we are traversing the stream to store and count the frequencies of the characters, which takes O(N) time.

Thus, the overall time complexity is O(N ^ 2).

Space Complexity

O(1), i.e. constant space complexity.

 

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