First Repeated Character
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

Question

First Repeated Character

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

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n^2)Explanation:

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

Python (3.5)

"""
    Time complexity: O(N ^ 2) 
    Space complexity: O(1)
    
    Where 'N' is the size of the string.
"""

def repeatedCharacter(str):
    # Initialise index to store the index of the first repeating character.
    index = -1

    # Start traversing through the string in order to check for each character.
    for i in range(len(str)):
        for j in range(i + 1, len(str)):
            # If first repeating character is found.
            if (str[i] == str[j]):
                # Store index of repeated character in the 'index'.
                index = i

                # Break as we only need to find the first repeating character.
                break
          
        """  
          If repeating character found and index updated .
          then we don't need to check for the rest of the string, so break.
        """
        if (index != -1):
            break

    """ 
      If index found before reaching the end of the string.
      then return the character at that index.
    """
    if(index >= 0):
        return str[index]
    # Else return '%' as asked in the problem statement.
    else:
        return '%'

Java (SE 1.8)

/*
	Time complexity: O(N ^ 2) 
	Space complexity: O(1)
	
    Where 'N' is the size of the string.
*/

public class Solution {
	public static char repeatedCharacter(String str) {
		// Initialise index to store the index of the first repeating character.
		int index = -1;

		// Start traversing through the string in order to check for each character.
		for (int i = 0; i < str.length(); i++) {
			for (int j = i + 1; j < str.length(); j++) {
				// If first repeating character is found.
				if (str.charAt(i) == str.charAt(j)) {
					// Store index of repeated character in the 'index'.
					index = i;

					// Break as we only need to find the first repeating character.
					break;
				}
			}
			/*
			   If repeating character found and index updated, 
			   then we don't need to check for the rest of the string, so break.
			*/
			if (index != -1) {
				break;
			}
		}
		/*
		   If index found before reaching the end of the string.
		   then return the character at that index.
		*/
		if (index >= 0) {
			return str.charAt(index);
		}
		// Else return '%' as asked in the problem statement.
		else {
			return '%';
		}
	}
}

C++ (g++ 5.4)

/*
    Time complexity: O(N ^ 2) 
    Space complexity: O(1)
    
    Where 'N' is the size of the string.
*/

#include

char repeatedCharacter(string &str){
    // Initialise index to store the index of the first repeating character.
	int index = -1;

    // Start traversing through the string in order to check for each character.
    for (int i = 0; i < str.size(); i++){
        for (int j = i + 1; j < str.size(); j++){
            // If first repeating character is found.
            if (str[i] == str[j]){
                // Store index of repeated character in the 'index'.
                index = i;
                // Break as we only need to find the first repeating character.
                break;
            }
        }
        /*
           If repeating character found and index updated.
           then we don't need to check for the rest of the string, so break.
        */
        if (index != -1){
            break;
        }
    }
    /*
       if index found before reaching the end of the string.
       then return the character at that index.
    */
    if(index >= 0){
        return str[index];
    }
    // Else return '%' as asked in the problem statement.
    else{
        return '%';
    }
}

Accepted Answer

Using Hash Table

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’

Space Complexity: O(1)Explanation:

O(1)

Since we are using a hash array of size 26, making the space complexity to be O(26), which is equivalent to O(1). So, space complexity will be O(1).

Time Complexity: O(n)Explanation:

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

Since we need to traverse through the complete string two times, once two stores the frequency and another time to check for the character. So, the time complexity will be. O(2 * N), which is equivalent to O(N).

Java (SE 1.8)

/*
	Time complexity: O(N) 
	Space complexity: O(1)
	
    Where 'N' is the size of the string.
*/

public class Solution {
	public static char repeatedCharacter(String str) {
		// Initialise a hash table of size 26.
		int[] hashTable = new int[26];

		for (int i = 0; i < 26; i++) {
			hashTable[i] = 0;
		}

		// Traverse through the string and store the frequency of each character of the string in the hash table.
		for (int i = 0; i < str.length(); i++) {
			hashTable[str.charAt(i) - 'a']++;
		}

		// Traverse again through the string checking for the frequencies of each character.
		for (int i = 0; i < str.length(); i++) {
			// If repeating character is found then return it.
			if (hashTable[str.charAt(i) - 'a'] > 1) {
				return str.charAt(i);
			}
		}
		// If no repeating character is found then return '%' as asked in the problem statement.
		return '%';
	}
}

C++ (g++ 5.4)

/*
    Time complexity: O(N) 
    Space complexity: O(1)
    
    Where 'N' is the size of the string.
*/

char repeatedCharacter(string &str){
    // Initialise a hash table of size 26.
    int hashTable[26] = {0};

    // Traverse through the string and store the frequency of each character of the string in the hash table.
    for(int i = 0; i < str.size(); i++){
        hashTable[str[i] - 'a']++;
    }

    // Traverse again through the string checking for the frequencies of each character.
    for(int i = 0; i < str.size(); i++){
        // If repeating character is found then return it.
        if(hashTable[str[i] - 'a'] > 1){
            return str[i];
        }
    }
    // If no repeating character is found then return '%' as asked in the problem statement.
    return '%';
}

Python (3.5)

"""
    Time complexity: O(N) 
    Space complexity: O(1)
    
    Where 'N' is the size of the string.
"""

def repeatedCharacter(str):
    # Initialise a hash table of size 26.
    hashTable = [0 for i in range(26)]

    # Traverse through the string and store the frequency of each character of the string in the hash table.
    for i in range(len(str)):
        hashTable[ord(str[i]) - ord('a')] += 1
    
    # Traverse again through the string checking for the frequencies of each character.
    for i in range(len(str)):
        # If repeating character is found then return it.
        if(hashTable[ord(str[i]) - ord('a')] > 1):
            return str[i]
    
    # If no repeating character is found then return '%' as asked in the problem statement.
    return '%'

Accepted Answer

Observation

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

Space Complexity: O(1)Explanation:

O(1).

Since we are using a bool array of size 26, making the space complexity to be O(26), which is equivalent to O(1). So, space complexity will be O(1).

Time Complexity: O(n)Explanation:

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

Since we need to traverse through the complete string only once. So, the time complexity will be O(N).

Python (3.5)

"""
    Time complexity: O(N) 
    Space complexity: O(1)
    
    Where 'N' is the size of the string.
"""

def repeatedCharacter(str):
    # Create a boolean array to store weather the character is visited or not.
    visited = [False for i in range(26)]

    # Initialise index to store the index of the first repeating character.
    index = -1

    # Traverse from right and update the index as soon as we see a visited character.
    lst = []
    for i in range(len(str)):
        lst.append(i)
    lst.reverse()

    for i in lst:
        """
          If you come through a character for the first time, mark it as visited.
          So that once you visit it again it will be already visited and you can store its index.
        """
        if (visited[ord(str[i]) - ord('a')] == False): 
            visited[ord(str[i]) - ord('a')] = True
        
        else:
            index = i
         
    
    # If index found before reaching the end of the string, then return the character at that index.
    if(index >= 0):
        return str[index]
    
    # Else return '%' as asked in the problem statement.
    else:
        return '%'

C++ (g++ 5.4)

/*
    Time complexity: O(N) 
    Space complexity: O(1)
    
    Where 'N' is the size of the string.
*/

char repeatedCharacter(string &str){
    // Create a boolean array to store weather the character is visited or not.
    bool visited[26]; 

    // Traverse through the boolean array and mark all as not visited.
    for (int i = 0; i < 26; i++){
        // 'false' means the character has not been visited.
        visited[i] = false; 
    }

    // Initialise index to store the index of the first repeating character.
	int index = -1;

    // Traverse from right and update the index as soon as we see a visited character.
    for (int i = str.size() - 1; i >= 0; i--){   
        /*
           If you come through a character for the first time, mark it as visited.
           So that once you visit it again it will be already visited and you can store its index.
        */
        if (visited[str[i] - 'a'] == false){
            visited[str[i] - 'a'] = true; 
        }
        else{
            index = i;
        } 
    } 
    // If index found before reaching the end of the string, then return the character at that index.
    if(index >= 0){
        return str[index];
    }
    // Else return '%' as asked in the problem statement.
    else{
        return '%';
    }
}

Java (SE 1.8)

/*
	Time complexity: O(N) 
	Space complexity: O(1)
	
    Where 'N' is the size of the string.
*/

public class Solution {
	public static char repeatedCharacter(String str) {
		// Create a boolean array to store weather the character is visited or not.
		boolean[] visited = new boolean[26];

		// Traverse through the boolean array and mark all as not visited.
		for (int i = 0; i < 26; i++) {
			// 'false' means the character has not been visited.
			visited[i] = false;
		}

		// Initialise index to store the index of the first repeating character.
		int index = -1;

		// Traverse from right and update the index as soon as we see a visited character..
		for (int i = str.length() - 1; i >= 0; i--) {
			/*
			   If you come through a character for the first time, mark it as visited.
			   So that once you visit it again it will be already visited and you can store its index.
			*/
			if (visited[str.charAt(i) - 'a'] == false) {
				visited[str.charAt(i) - 'a'] = true;
			} else {
				index = i;
			}
		}
		// If index found before reaching the end of the string then return the character at that index.
		if (index >= 0) {
			return str.charAt(index);
		}
		// Else return '%' as asked in the problem statement.
		else {
			return '%';
		}
	}
}

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

Example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Delhivery Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer