Given a string str of length n (1 <= n <= 106) and a number k, the task is to find the kth non-repeating character in the string.
Examples:
Input : str = geeksforgeeks, k = 3
Output : r
Explanation: First non-repeating character is f, second is o and third is r.
Input : str = geeksforgeeks, k = 2
Output : o
Input : str = geeksforgeeks, k = 4
Output : Less than k non-repeating characters in input.
This problem is mainly an extension of the First non-repeating character problem.
K’th Non-repeating Character using Nested Loop:
A Simple Solution is to run two loops. Start traversing from the left side. For every character, check if it repeats or not. If the character doesn’t repeat, increment the count of non-repeating characters. When the count becomes k, return the character.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>
using namespace std;
char kthNonRepeatingChar(string str, int k)
{
int count = 0;
char result = '\0' ;
for ( int i = 0; i < str.length(); i++) {
bool repeating = false ;
for ( int j = 0; j < i; j++) {
if (str[j]==str[i])
{
repeating = true ;
}
}
for ( int j = i + 1; j < str.length(); j++) {
if (str[i] == str[j]) {
repeating = true ;
}
}
if (!repeating) {
count++;
if (count == k) {
result = str[i];
break ;
}
}
}
return result;
}
int main()
{
string str = "geeksforgeeks" ;
int k = 3;
char result = kthNonRepeatingChar(str, k);
if (result == '\0' ) {
cout << "There is no kth non-repeating character "
"in the string.\n" ;
}
else {
cout << "The " << k
<< "th non-repeating character in the string "
"is "
<< result << ".\n" ;
}
return 0;
}
|
Java
import java.util.*;
public class Main {
public static char kthNonRepeatingChar(String str,
int k)
{
int count = 0 ;
char result = '\0' ;
for ( int i = 0 ; i < str.length(); i++) {
boolean repeating = false ;
for ( int j = i + 1 ; j < str.length(); j++) {
if (str.charAt(i) == str.charAt(j)) {
repeating = true ;
break ;
}
}
if (!repeating) {
count++;
if (count == k) {
result = str.charAt(i);
break ;
}
}
}
return result;
}
public static void main(String[] args)
{
String str = "geeksforgeeks" ;
int k = 3 ;
char result = kthNonRepeatingChar(str, k);
if (result == '\0' ) {
System.out.println(
"There is no kth non-repeating character "
+ "in the string." );
}
else {
System.out.println(
"The " + k
+ "th non-repeating character in the string "
+ "is " + result + "." );
}
}
}
|
Python3
def kthNonRepeatingChar(s: str , k: int ) - > str :
count = 0
result = '\0'
for i in range ( len (s)):
repeating = False
for j in range (i + 1 , len (s)):
if s[i] = = s[j]:
repeating = True
break
if not repeating:
count + = 1
if count = = k:
result = s[i]
break
return result
if __name__ = = '__main__' :
s = "geeksforgeeks"
k = 3
result = kthNonRepeatingChar(s, k)
if result = = '\0' :
print ( "There is no kth non-repeating character "
"in the string." )
else :
print (f "The {k}th non-repeating character in the string "
f "is {result}." )
|
C#
using System;
public class Program {
static char kthNonRepeatingChar( string str, int k)
{
int count = 0;
char result = '\0' ;
for ( int i = 0; i < str.Length; i++) {
bool repeating = false ;
for ( int j = i + 1; j < str.Length; j++) {
if (str[i] == str[j]) {
repeating = true ;
break ;
}
}
if (!repeating) {
count++;
if (count == k) {
result = str[i];
break ;
}
}
}
return result;
}
static void Main( string [] args)
{
string str = "geeksforgeeks" ;
int k = 3;
char result = kthNonRepeatingChar(str, k);
if (result == '\0' ) {
Console.WriteLine(
"There is no kth non-repeating character "
+ "in the string." );
}
else {
Console.WriteLine(
"The " + k
+ "th non-repeating character in the string is "
+ result + "." );
}
}
}
|
Javascript
function kthNonRepeatingChar(str, k) {
let count = 0;
let result = "\0" ;
for (let i = 0; i < str.length; i++) {
let repeating = false ;
for (let j = i + 1; j < str.length; j++) {
if (str[i] == str[j]) {
repeating = true ;
break ;
}
}
if (!repeating) {
count++;
if (count == k) {
result = str[i];
break ;
}
}
}
return result;
}
let str = "geeksforgeeks" ;
let k = 3;
let result = kthNonRepeatingChar(str, k);
if (result == "\0" ) {
console.log( "There is no kth non-repeating character in the string." );
} else {
console.log(`The ${k}th non-repeating character in the string is ${result}`);
}
|
Output
The 3th non-repeating character in the string is r.
Time Complexity: O(n²)
Auxiliary Space: O(1)
K’th Non-repeating Character using Hashing:
- Create an empty hash map to store character counts.
- Loop through the string and update the counts of each character in the hash map.
- Loop through the string again and find the kth non-repeating character by checking the count of each character in the hash map.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>
using namespace std;
char kthNonRepeatingChar(string str, int k)
{
unordered_map< char , int > charCounts;
for ( int i = 0; i < str.length(); i++) {
charCounts[str[i]]++;
}
int nonRepeatingCount = 0;
for ( int i = 0; i < str.length(); i++) {
if (charCounts[str[i]] == 1) {
nonRepeatingCount++;
if (nonRepeatingCount == k) {
return str[i];
}
}
}
return '\0' ;
}
int main()
{
string str = "geeksforgeeks" ;
int k = 3;
char result = kthNonRepeatingChar(str, k);
if (result == '\0' ) {
cout << "There is no kth non-repeating character "
"in the string.\n" ;
}
else {
cout << "The " << k
<< "th non-repeating character in the string "
"is "
<< result << ".\n" ;
}
return 0;
}
|
Java
import java.util.*;
public class Main {
public static char kthNonRepeatingChar(String str, int k) {
Map<Character, Integer> charCounts = new HashMap<>();
for ( int i = 0 ; i < str.length(); i++) {
char c = str.charAt(i);
charCounts.put(c, charCounts.getOrDefault(c, 0 ) + 1 );
}
int nonRepeatingCount = 0 ;
for ( int i = 0 ; i < str.length(); i++) {
char c = str.charAt(i);
if (charCounts.get(c) == 1 ) {
nonRepeatingCount++;
if (nonRepeatingCount == k) {
return c;
}
}
}
return '\0' ;
}
public static void main(String[] args) {
String str = "geeksforgeeks" ;
int k = 3 ;
char result = kthNonRepeatingChar(str, k);
if (result == '\0' ) {
System.out.println( "There is no kth non-repeating character " +
"in the string." );
} else {
System.out.println( "The " + k + "th non-repeating character " +
"in the string is " + result + "." );
}
}
}
|
Python3
def kth_non_repeating_char(string, k):
char_counts = {}
for char in string:
if char in char_counts:
char_counts[char] + = 1
else :
char_counts[char] = 1
non_repeating_count = 0
for char in string:
if char_counts[char] = = 1 :
non_repeating_count + = 1
if non_repeating_count = = k:
return char
return None
if __name__ = = "__main__" :
string = "geeksforgeeks"
k = 3
result = kth_non_repeating_char(string, k)
if result is None :
print ( "There is no kth non-repeating character in the string." )
else :
print (f "The {k}th non-repeating character in the string is {result}." )
|
C#
using System;
using System.Collections.Generic;
class Gfg
{
static char kthNonRepeatingChar( string str, int k)
{
Dictionary< char , int > charCounts = new Dictionary< char , int >();
foreach ( char c in str)
{
if (charCounts.ContainsKey(c))
{
charCounts++;
}
else
{
charCounts = 1;
}
}
int nonRepeatingCount = 0;
foreach ( char c in str)
{
if (charCounts == 1)
{
nonRepeatingCount++;
if (nonRepeatingCount == k)
{
return c;
}
}
}
return '\0' ;
}
static void Main()
{
string str = "geeksforgeeks" ;
int k = 3;
char result = kthNonRepeatingChar(str, k);
if (result == '\0' )
{
Console.WriteLine( "There is no kth non-repeating character in the string." );
}
else
{
Console.WriteLine($ "The {k}th non-repeating character in the string is {result}." );
}
}
}
|
Javascript
function kthNonRepeatingChar(str, k) {
const charCounts = new Map();
for (let i = 0; i < str.length; i++) {
const char = str[i];
charCounts.set(char, (charCounts.get(char) || 0) + 1);
}
let nonRepeatingCount = 0;
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (charCounts.get(char) === 1) {
nonRepeatingCount++;
if (nonRepeatingCount === k) {
return char;
}
}
}
return '\0' ;
}
function main() {
const str = "geeksforgeeks" ;
const k = 3;
const result = kthNonRepeatingChar(str, k);
if (result === '\0' ) {
console.log( "There is no kth non-repeating character in the string." );
} else {
console.log(`The ${k}th non-repeating character in the string is ${result}.`);
}
}
main();
|
Output
The 3th non-repeating character in the string is r.
Time Complexity: O(n)
Auxiliary Space: O(1)
This article is contributed by Aarti_Rathi and Shivam Gupta. If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!