Kth Non-repeating Character

Problem Statement

In the “Kth Non-repeating Character” we have given a string “s”. Write a program to find out the kth non-repeating_character. If there are less than k character which is non-repeating in the string then print “-1”.

Input Format

The first and only one line containing a string “s”.

Output Format

The first and only one line containing a_character that represents the kth non-repeating_character. If there are less than k character which is non-repeating in the string then print “-1”.

Example

tutorialcup
3

i

Explanation: Here freq[t] is 2, freq[u] is 2, and the rest of the other char having freq 1. So the Kth non-repeating_character is “o”.

Algorithm

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

2. Create an index array to store the index of non-repeating characters.

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 the length of the 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.

Implementation

C++ Program to find the Kth Non-repeating Character

#include <bits/stdc++.h>
using namespace std;

int main()
{
   string s;
   cin>>s;
   int k;
   cin>>k;
   int n=s.length();
   int count[256];
   int index[256];
   memset(count,0,sizeof(count));
   for(int i=0;i<256;i++)
   {
       index[i]=n;
   }
   for(int i=0;i<n;i++)
   {
        count[s[i]]++;
        if(count[s[i]]==1)
        {
            index[s[i]]=i;
        }
        if(count[s[i]]==2)
        {
            index[s[i]]=n;
        }
   }
   sort(index, index+256);
    if(index[k-1]!=n)
    {
        cout<<s[index[k-1]]<<endl;  
    }
    else
    {
        cout<<-1<<endl;
    }
   return 0;
}

Java Program to find the Kth Non-repeating Character

import java.util.Arrays;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int k=sr.nextInt();
                int n=s.length();
                int freq[] = new int [256];
                int index[] = new int [256];
                for(int i=0;i<256;i++)
                {
                    freq[i]=0;
                    index[i]=n;
                }
                for(int i=0;i<n;i++) 
                {
                    freq[s.charAt(i)]++; 
                    if(freq[s.charAt(i)]==1) 
                    { 
                        index[s.charAt(i)]=i; 
                    } 
                    if(freq[s.charAt(i)]==2) 
                    {
                        index[s.charAt(i)]=n;
                    }
                }
                Arrays.sort(index);
                if(index[k-1]!=n) 
                {
                    System.out.println(s.toCharArray()[index[k-1]]); 
                }
                else
                {
                    System.out.println(-1); 
                }
  } 
} 

tutorialcup
3

i

Complexity Analysis to find the Kth Non-repeating Character

Time Complexity

O(n) where n is the size of the given array. Here we simply traverse the given string “s” and count the frequency of each character. After that perform some operation as required in constant time.

Space Complexity

O(1) because here we only use the constant space of 256 sizes. Here we store the frequency and index of each character.