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