Home » Interview Questions » String Interview Questions » Kth Non-repeating character

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

READ  Letter Case Permutation

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions