Kth Non-repeating character

In the given string, find the kth non-repeating character.

Example

Input string : “tutorial-cup”
K = 3
Kth non-repeating character is o

Time complexity : O(n)

Algorithm

1. Create count array to store the count of characters in the array.

2. Create index array to store index of non-repeating character.

3. If a character ‘x’ is repeating or not present in string store n in the index array.

4. Initialize count array with zeroes and index array with n. (n is length of string)

5. Traverse the input string x= str[i]

6. Increment count[x]

7. If count[x] = 1, then store index of x in index[x]. index[x] = i

8. If count[x] = 2, then remove x from index[]. Index[x] = n.

9. Sort the index array.

10. Index[k] is the kth non-repeating character.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
int KthNonRepeating(string input_string, int k)
{
    int n = input_string.length();
    int count[256];//count array
    int index[256];//Index array
    for (int i = 0; i < 256; i++)//Initialize count and index array
    {
        count[i] = 0;
        index[i] = n;  
    }
    // Traverse the input string
    for (int i = 0; i < n; i++)
    {
        char x = input_string[i];
        count[x] = count[x] + 1;
        //if its first apperence
        //Set as its index in index array
        if (count[x] == 1)
        {
            index[x] = i;
        }
        //If count is 2
        //Remove it from index array
        if (count[x] == 2)
        {
            index[x] = n;
        }
    }
    //Sort index array
    sort(index, index+256);
    if(index[k-1] != n)
    {
      return index[k-1];  
    }
    else
    {
        return -1;
    }
}
 
//Main function
int main()
{
   string input_string = "tutorial-cup";
   int k = 3;
   int result = KthNonRepeating(input_string, k);
   if (result == -1)
   {
       cout<<"There are less than k non-repeating characters";
   }
   else
   {
       cout<<"Kth non-repeating character is: "<<input_string[result];
   }
   return 0;
}
Try It

 


Next > < Prev
Scroll to Top