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

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

Question

First Unique Character in a String

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

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.

Accepted Answer

1. Make hash_map which will map the character to there frequencies.
2. Traverse the string.
3. Increase the count of current character.
4. Traverse the string again and check whether the current character frequency=1.
5. Print that first character which have frequency 1.

Accepted Answer

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:

Make a count array that will map the character to their respective frequencies.
Traverse the given string.
Increase the count of the current character in the count array.
Now traverse the string again and check whether the current character has frequency=1.
If the frequency>1, continue the traversal.
Else break the loop and add the current character in the arraylist.

Space Complexity: O(1)Explanation:

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

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

Time Complexity: O(1)Explanation:

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

Accepted Answer

Count array and single string traversal

Make a count array to store the index of the character if it appears only once; else, it stores a negative value. So when it comes to finding the first non-repeating character, we have to scan the count array instead of the string.

Below is the algorithm:

Make a count array and initialize all characters by -1, i.e., all considered as absent.
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.
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.
Add the character present at the result index in the arraylist.

Space Complexity: O(1)Explanation:

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

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

Time Complexity: O(1)Explanation:

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 the index of the characters, which takes O(N) time.

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

Accepted Answer

Optimized Approach

We can use a Doubly Linked List to get the first non-repeating character from a stream efficiently. This can be done by storing all non-repeating characters in DLL. We will keep them in order, i.e., the head node of DLL contains the first non-repeating character, and the next node contains the next non-repeating character, and so on. We will also maintain two ArrayLists: the first one maintains characters that are already visited two or more times, the second one is stores pointers to linked list nodes.

Following is the algorithm to implement the above logic:

Create an empty doubly linked list DLL, a boolean array ISCHARREPEATED of size 256, and another ArrayList RESULT. In DLL, we store pointers to DLL nodes.
For all characters CH, ISCHARREPEATED[CH] is true if x is repeated two or more times, otherwise false. DLL[CH] contains a pointer to a DLL node if the character CH is present in DLL, otherwise NULL.
Initialize all values of DLL as NULL and ISCHARREPEATED[] as false.
To get the first non-repeating character, return the character at the head of DLL.
Iterate over given stream of characters, for each 0 ≤ i ≤ STREAM.LENGTH() and do:
1. Initialize character TEMP to STREAM[i].
2. Process 'TEMP' only if it has occurred at most once, i.e., if ISCHARREPEATED[TEMP] is false, add TEMP to DLL if DLL does not contain TEMP. Else remove TEMP from DLL and make ISCHARREPEATED[TEMP] false.
Add the current first non-repeating character from the stream in the resultant ArrayList RESULT.
Return RESULT.

Space Complexity: O(1)Explanation:

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

Since we are using an arraylist to store the pointer to a DLL node, which can have a maximum size of ‘N’ pointers.

Thus, the final space complexity is O(N).

Time Complexity: O(1)Explanation:

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

Since we are traversing the stream only once to store all the non-repeating characters using DLL, which takes O(1) time to add or remove a node.

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

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:

Input Format:

Output Format:

Note:

Constraints:

Top Amdocs Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amdocs Software Developer