Repeated Character in a string

 Given a string consisting of lowercase English alphabets. Find the first repeated character in the string. In case there's no repeating character present, return '#'.



Example 1:
Input:
S = "codemummycode"
Output: c
Explanation: c, o, d,e and m are the repeating
characters. Out of these, c occurs first. 

Example 2:
Input: 
S = "abcde"
Output: #
Explanation: No repeating character present.


method 1:

Simple Solution: The solution is to run two nested loops. Start traversing from left side. For every character, check if it repeats or not. If the character repeats, return the character.

Time Complexity of this solution is O(n2)


method 2:

c++ implementation:

 char firstRep (string s)
    {
        int h[26]={0};
        
        for(int i=0;i<s.length();i++)
        h[s[i]-'a']++;
        
        for(int i=0;i<s.length();i++)
        {
           if( h[s[i]-'a']>1)
           return s[i];
        }
       
        return '#';
    }

 Time Complexity: O(n).   where n is no. of characters in the string
Auxiliary Space: O(1).




method 3:

  • Create an unordered_set.
  • Scan each character of the input string and insert values in the set
  • When any character appears more than once,  return the character.

c++ implementation:

// Returns first repeating character in str. 
char firstRepeating(string &str) 
    // Creates an empty hashset 
    unordered_set<char> h; 
  
    // Traverse the input array from left to right 
    for (int i=0; i<str.length(); i++) 
    { 
        char c = str[i]; 
  
        // If element is already in hash set, update x 
        // and then break 
        if (h.find(c) != h.end()) 
            return c; 
  
        else // Else add element to hash set 
            h.insert(c); 
    } 
  
    // If there was no repeated character 
    return '\0'; 

 Time Complexity: O(n).   where n is no. of characters in the string
Auxiliary Space: O(n).

darkmode