Repeated Character

Problem

Given a string consisting of lowercase english alphabets. Find the repeated character present first in the string.

NOTE: If there are no repeating characters return '#'.

Examples:

Example 1:

Input:
S = "geeksforgeeks"
Output: g
Explanation: g, e, k and s are the repeating characters. Out of these, g occurs first. 

Example 2:

Input: 
S = "abcde"
Output: -1
Explanation: No repeating character present. (You need to return '#')

Your task:

You don't need to read input or print anything. Your task is to complete the function firstRep() which takes the string S as input and returns the the first repeating character in the string. In case there's no repeating character present, return '#'.

• Expected Time Complexity: $O(|S|)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=|S|<=10^5$

Solution

Python

def firstRep(self, s):
    char_count = {}
    for index, char in enumerate(s):
        if char in char_count:
            char_count[char]['count'] += 1
        else:
            char_count[char] = {'count': 1, 'index': index}
    first_repeated = '#'
    min_index = float('inf')
    for char in s:
        if char_count[char]['count'] > 1 and char_count[char]['index'] < min_index:
            first_repeated = char
            min_index = char_count[char]['index']
    return first_repeated

Java

char firstRep(String S) {
    char []str=S.toCharArray();
    for(int i=0;i<str.length;i++) {
        for(int j=i;j<str.length;j++) {
            if(i!=j) {
                if(str[i]==str[j]) {
                     return str[i];
                }
            }
        }
    }
    return '#';
}

C++

char firstRep (string s) {
    unordered_map<char,int>m;
    for(char c:s) {
        m[c]++;
    }
    for(char c:s) {
        if(m[c]>1) {
            return c;
        }
    }
    return '#';
}

C

char firstRep(const char *s) {
    Entry hashmap[256] = {0}; 
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        hashmap[s[i]].key = s[i];
        hashmap[s[i]].count++;
    }
    for (int i = 0; i < len; i++) {
        if (hashmap[s[i]].count > 1) {
            return s[i];
        }
    }
    return '#'; /
}

• Time Complexity: $O(|S|)$
• Auxiliary Space: $O(1)$