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;
}
