Print first non-repeating character in the string

Given a String where characters are repeating. Write code to print the first character that is repeating later in the string. e.g,

Input String: ritambhara
Output: i
Input String: social ritambhara
Output: s

Solution:

There are multiple questions that works on hashing and counting of characters in a string. See previous problems “Print character repeating maximum numberr of times in a string“, “Find first non-repeating character in the string“, “Find all repeating characters in a string“..

The solution for this problem is on similar lines..

Algorithm:

1. Keep a count array which will store the number of times a character is repeating in the array.
2. Initially all the counts will be zero.
3. Traverse the string, for each character in the string, increment the corresponding count.
4. Traverse the string again, and return the first character for which count is 1.

Code:

/**
 * Returns the first non-repeating character.
 */
char printNonRepeating(char* str)
{
    // Boundary check
    if(str == NULL || str[0] == '\0')
    {
        printf("EMPTY STRING");
        return NULL;
    }
    // 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)
            return str[i];
    // If no non-repeating character
    return NULL;
}

Time Complexity: O(n)
Extra Space: O(1).. in fact is it O(256) in this case because we are using the count array. But since that in independent of the size of input array, hence O(1).

Method-2: Brute force (without hashing)

If you have strict memory requirements and you cannot afford to have the count array. Then the brute force method is to check the entire string for each character and see if that character is present in the string or not.

Code:

char printNonRepeating(char* str)
{
    // Boundary check
    if(str == NULL || str[0] == '\0')
    {
        printf("EMPTY STRING");
        return;
    }
    for(int i = 0; str[i] != '\0';  i++)
    {
        bool found = false;
        for(int j=i+1; str[j] != '\0'; j++)
        {
            if(str[i] == str[j])
            {
                found = true;
                break; // No need to check further.
            }
        }
        if(!found)
            return str[i];
    }
    // No non-repeating character found
    return NULL;
}

Time Complexity:

Worst Case: O(n²)
Best Case: O(1). When the first character is repeating at second position itself.

Extra Space: O(1).