Print the first repeating character in String

Give a string in which characters may be repeating. Print the first character (from the start) which is repeating in the string. For example:

String: ABCBCD
Output: B (A is not repeating, hence B is the first character which is repeating)
String: ABCDE
Output: NULL (No character repeating)

Bruite-Force Method:

For each character, Check if it is present in the String after it. If found then print the character and return, else continue. If end of string is reached, then there is no repeating character.

Code:

void printRepeating(char* str)
{
    // Boundary check
    if(str == NULL || str[0] == '\0')
    {
        printf("EMPTY STRING");
        return;
    }
    for(int i = 0; str[i] != '\0';  i++)
    {
        for(int j=i+1; str[j] != '\0'; j++)
        {
            if(str[i] == str[j])
            {
                printf("%c", str[i]);
                return;
            }
        }
    }
}

Time Complexity:

Worst Case: O(n²) – In case of no repeatition.
Best Case: O(1) – When the first element is repeating at the second position

Extra Space: O(1) – It is more than the brute-force method, because we need a count array also. But count array is taking constant amount of memory (O(256) in our case). Hence the total extra space will be O(1), i.e constant.

Hashing Method (Using Count Array):
In this problem also we will be using the count array, the way we used it in this problem. Count array will keep the count of number of times a character is repeated in the String. If string is ABCB, then

count[‘A’] = 1
count[‘B’] = 2
count[‘C’] = 1

Code:

void printRepeating(char* str)
{
    // Boundary check
    if(str == NULL || str[0] == '\0')
    {
        printf("EMPTY STRING");
        return;
    }
    // Count Array. All elements are zeros
    int cntArr[256] = {0};
    // Populating the Count Array
    for(int i = 0; str[i] != '\0';  i++)
        cntArr[str[i]]++;
    // Getting the index of Maximum count in the Array
    int maxCntIdx = 0;
    for(int i=0; str[i] != '\0';  i++)
        if(cntArr[str[i]] > 1)
        {
            printf(" %c ", str[i]);
            return;
        }
}

Time Complexity:

Worst Case: O(n) – In case of no repeatition.
Best Case: O(n) – Because we still need to create the count array.

Extra Space: O(1)

Variation:

Another variation to this problem can be to print the first non-repeating (or unique) character in the String. It is the complement of above problem. So we just need to print if the count == 1.

Extension:

An extension to this problem can be to print all the repeating characters in the string. This is not as simple as the above problem. Because if a character is repeated then we want to print it only once and not corresponding to each repetition of the character. For example: If the string is,  ABACDEB. then the output should be, A B, and not, A B A B.

This problem is handled in this post.

 Also See: Print all repeating characters in a string