Last Updated: 27 Feb, 2021
First Repeated Character
Moderate
Asked in companies
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.
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
Approaches
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.
- Check if the character at ‘i’ is equal to the character at ‘j’
- Start traversing with another variable from ‘j’ = ‘i’ to ‘j’ < length of string
- If no repeating character is found then return ‘-1’.
In this approach, we first store the frequencies of each character in a hash table. Then traverse again through the loop checking the frequencies and the first character whose frequency is more than 1, that means that the first character which repeats itself is returned.
The steps are as follows:
- Create a hash table of size 26 and initialise it with zero.
- Traverse through the string, storing the frequencies in the hash table.
- Traverse again through the array and when a character of frequency greater than ‘1’ is found, return it.
- If no character with a frequency greater than1’ is found then simply return ‘-1’
In this approach, we will traverse the string from right to left and keep a track of all the visited characters. If a character is repeated, we simply update the result and finally return the character at the result.
The steps are as follows:
- Mark all the characters in a bool array as not visited. The bool array is used to keep track of the visited numbers, so that if a number is visited again it can update the result. We start with all characters as not visited so that once a character is visited again it will change from “non_visited” to “visited”.
- Initialise a variable ‘RESULT’, that stores the index of the repeated character.
- Start traversing from end to start of string:
- Keep updating the characters as visited.
- Update ‘RESULT’ as soon as we come through a visited character.
- Return character at index ‘RESULT’ once you reach the start of the string.
- If no repeated character is found then, simply return ‘-1’.