# Kth Non-repeating character

0
194 ## 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;//count array
int index;//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;
}``````