First Repeated Character

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
13 upvotes
Asked in companies
EcomExpressDelhiveryAmazon

Problem statement

You are given a string 'STR' of lowercase English alphabets. You need to find the repeated character present first in the string.

Example: 
If the string is: “abccba”, then the first repeated character is ‘c’, but the repeated character that is present first in the string is ‘a’. You need to print ‘a’.
Note: 
Keep in mind that you need to print the repeated character that is present first in the string and not the first repeating character.
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 line of each test case will contain a string ‘S’, which denotes the string of lowercase English alphabets.
Output Format: 
For each test case, print the repeated character that occurs first in the string. If no repeated character is found then print ‘%’.

Output for every test case will be printed in a separate line.
Note: 
You don't need to print anything. It has already been taken care of. 

You just need to complete the “repeatedCharacter” function that returns the first repeating character in the string. In case there is no repeating character then return “%”.
Constraints: 
1 <= T <= 200
0 <= size of S <= 10000

where 'S’ is the string of lowercase English alphabets.

Time limit: 1 sec
Sample Input 1:
2
abccba
codingninjas
Sample Output 1:
a
i
Explanation of sample input 1:
In the first test case, 
The repeated character that occurs first in the string is ‘a’

In the second test case, 
The repeated character that occurs first in the string is ‘i’
Sample Input 2:
3
hello
helloh
abc
Sample Output 2:
l
h
%
Explanation for sample input 2:
In the first test case, 
The repeated character that occurs first in the string is ‘l’

In the second test case, 
The repeated character that occurs first in the string is ‘h’

In the third test case, 
There is no repeating character in the string, so print ‘%’
Hint

Can you think of comparing each character with every other character?

Approaches (3)
Brute Force

The basic approach is to check each character in the rest of the string and if it is repeated then simply print it.

 

The steps are as follows:

 

  • Start traversing through the string from ‘i’ = 0 to ‘i’ < length of string
    • Start traversing with another variable from ‘j’ = ‘i’ to ‘j’ < length of string
      • Check if the character at ‘i’ is equal to the character at ‘j’
        • If yes then return it.
        • If no, then continue.
  • If no repeating character is found then return ‘-1’.
Time Complexity

O(N ^ 2), Where ‘N’ is the size of the string.

 

Since we are traversing each pair of characters in the given string using a nested loop running in O(N) time each. So, the time complexity will be O(N ^ 2).

Space Complexity

O(1)

 

Since no extra space is required. So, space complexity will be O(1).

Code Solution
(100% EXP penalty)
First Repeated Character
Full screen
Console