First non repeating character

Easy

0/40

Average time to solve is 15m

64 upvotes

Asked in companies

Problem statement

Ninja is now bored with numbers and is now playing with characters but hates when he gets repeated characters. Ninja is provided a string, and he wants to return the first unique character in the string.The string will contain characters only from the English alphabet set, i.e., ('A' - 'Z') and ('a' - 'z'). If there is no non-repeating character, print the first character of the string. If there is no non-repeating character, return the first character of the string.

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

Input Format:

The first line contains a single integer T representing the number of test cases. 

The first and the only line of each test case will contain the input string.

Output Format:

For each test case, print a character denoting the first non-repeating character in the input string.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= Length of Input String <= 10^4

Time Limit: 1 sec

Sample Input 1 :

2
aDcadhc
AabBcC

Sample Output 1:

 D
 A

Explanation for Sample Input 1:

In the first test case, ‘a’ is repeated.’ D’ is the first non-repeating character in the string, so we return it.

In the second test case, all the characters are non-repeating, so we return the first character.

Sample Input 2 :

 2
 ABcd
 AAAbcdb

Sample Output 2:

 A
 c

Hint 1

Hint 2

Can you traverse the whole array sequentially?

Approaches (2)

Approach 1

Approach 2

Brute force

We will traverse the whole array and check if that element previously occurred or not.

The steps are as follows:

We will iterate over all the elements of the array, i.e., i = 0 to i = N - 1:
- We will iterate over all the elements of the array excluding the present element, i.e., j = 0 to i = N - 1:
  - If we get that for no j, S[i] equals S[j], then we return S[i].
We will return the first character of the string if the loop completes and no answer is returned.

Time Complexity

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

As we keep a character fixed and checked for all values from1 to ‘N’, there are at most ‘N^2’ iterations. Hence the overall complexity is O(N^2).

Space Complexity

O(1), no extra space required.

As we are not using any extra space. Hence, the overall space complexity is O(1)

(100% EXP penalty)

First non repeating character

Console