K'th Non-repeating Character - GeeksforGeeks

K'th Non-repeating Character - GeeksforGeeks
Given a string and a number k, find the k'th non-repeating character in the string. Consider a large input string with lacs of characters and a small character set. How to find the character by only doing only one traversal of input string?

Method 3 (O(n) and requires one traversal)
The idea is to use two auxiliary arrays of size 256 (Assuming that characters are stored using 8 bits). The two arrays are:

count[x] : Stores count of character 'x' in str.
           If x is not present, then it stores 0.

index[x] : Stores indexes of non-repeating characters
           in str. If a character 'x' is not  present
           or x is repeating, then it stores  a value
           that cannot be a valid index in str[]. For 
           example, length of string.

1. Initialize all values in count[] as 0 and all values in index[] as n where n is length of string.
2. Traverse the input string str and do following for every character c = str[i].
   • Increment count[x].
   • If count[x] is 1, then store index of x in index[x], i.e., index[x] = i
   • If count[x] is 2, then remove x from index[], i.e., index[x] = n
3. Now index[] has indexes of all non-repeating characters. Sort index[] in increasing order so that we get k’th smallest element at index[k]. Note that this step takes O(1) time because there are only 256 elements in index[].

int kthNonRepeating(string str, int k)

{

    int n = str.length();

 

    // count[x] is going to store count of

    // character 'x' in str. If x is not present,

    // then it is going to store 0.

    int count[MAX_CHAR];

 

    // index[x] is going to store index of character

    // 'x' in str.  If x is not  present or x is

    // repeating, then it is going to store  a value

    // (for example, length of string) that cannot be

    // a valid index in str[]

    int index[MAX_CHAR];

 

    // Initialize counts of all characters and indexes

    // of non-repeating  characters.

    for (int i = 0; i < MAX_CHAR; i++)

    {

        count[i] = 0;

        index[i] = n;  // A value more than any index

                       // in str[]

    }

 

    // Traverse the input string

    for (int i = 0; i < n; i++)

    {

        // Find current character and increment its

        // count

        char x = str[i];

        ++count[x];

 

        // If this is first occurrence, then set value

        // in index as index of it.

        if (count[x] == 1)

            index[x] = i;

 

        // If character repeats, then remove it from

        // index[]

        if (count[x] == 2)

            index[x] = n;

    }

 

    // Sort index[] in increasing order.  This step

    // takes O(1) time as size of index is 256 only

    sort(index, index+MAX_CHAR);

 

    // After sorting, if index[k-1] is value, then

    // return it, else return -1.

    return (index[k-1] != n)? index[k-1] : -1;

}

Method 1 (Simple : O(n2)
A Simple Solution is to run two loops. Start traversing from left side. For every character, check if it repeats or not. If the character doesn’t repeat, increment count of non-repeating characters. When the count becomes k, return the character.

Method 2 (O(n) but requires two traversals)

1. Create an empty hash.
2. Scan input string from left to right and insert values and their counts in the hash.
3. Scan input string from left to right and keep count of characters with counts more than 1. When count becomes k, return the character.

Read full article from K'th Non-repeating Character - GeeksforGeeks