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:
#include <bits/stdc++.h>
using namespace std;
char kthNonRepeatingChar(string str, int k)
{
// Create an empty hash map to store the counts of each
// character in the string
unordered_map<char, int> charCounts;
// Loop through the string and store the counts of each
// character in the hash map
for (int i = 0; i < str.length(); i++) {
charCounts[str[i]]++;
}
// Loop through the string and find the kth
// non-repeating character
int nonRepeatingCount = 0;
for (int i = 0; i < str.length(); i++) {
if (charCounts[str[i]] == 1) {
nonRepeatingCount++;
if (nonRepeatingCount == k) {
// When the count of non-repeating
// characters equals k, return the character
return str[i];
}
}
}
// If there is no kth non-repeating character in the
// string, return the null character
return '\0';
}
int main()
{
string str = "w3wiki";
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;
}
import java.util.*;
public class Main {
public static char kthNonRepeatingChar(String str, int k) {
// Create an empty hash map to store the counts of each
// character in the string
Map<Character, Integer> charCounts = new HashMap<>();
// Loop through the string and store the counts of each
// character in the hash map
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
}
// Loop through the string and find the kth
// non-repeating character
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) {
// When the count of non-repeating
// characters equals k, return the character
return c;
}
}
}
// If there is no kth non-repeating character in the
// string, return the null character
return '\0';
}
public static void main(String[] args) {
String str = "w3wiki";
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 + ".");
}
}
}
# Python code of the above approach
def kth_non_repeating_char(string, k):
# Create an empty dictionary to store
# the counts of each character in the string
char_counts = {}
# Loop through the string and store
# the counts of each character in the dictionary
for char in string:
if char in char_counts:
char_counts[char] += 1
else:
char_counts[char] = 1
# Loop through the string and find the kth non-repeating character
non_repeating_count = 0
for char in string:
if char_counts[char] == 1:
non_repeating_count += 1
if non_repeating_count == k:
# When the count of non-repeating
# characters equals k, return the character
return char
# If there is no kth non-repeating character in the string, return None
return None
# Main function
if __name__ == "__main__":
string = "w3wiki"
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}.")
# This code is contributed by Susobhan Akhuli
using System;
using System.Collections.Generic;
class Gfg
{
static char kthNonRepeatingChar(string str, int k)
{
// Create a dictionary to store the counts of each character in the string
Dictionary<char, int> charCounts = new Dictionary<char, int>();
// Loop through the string and store
// the counts of each character in the dictionary
foreach (char c in str)
{
if (charCounts.ContainsKey(c))
{
charCounts[c]++;
}
else
{
charCounts[c] = 1;
}
}
// Loop through the string and find
// the kth non-repeating character
int nonRepeatingCount = 0;
foreach (char c in str)
{
if (charCounts[c] == 1)
{
nonRepeatingCount++;
if (nonRepeatingCount == k)
{
// When the count of non-repeating characters equals k, return the character
return c;
}
}
}
// If there is no kth non-repeating character in the string, return the null character
return '\0';
}
static void Main()
{
string str = "w3wiki";
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}.");
}
}
}
function kthNonRepeatingChar(str, k) {
// Create an empty map to store the counts of each
// character in the string
const charCounts = new Map();
// Loop through the string and store the counts of each
// character in the map
for (let i = 0; i < str.length; i++) {
const char = str[i];
charCounts.set(char, (charCounts.get(char) || 0) + 1);
}
// Loop through the string and find the kth non-repeating character
let nonRepeatingCount = 0;
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (charCounts.get(char) === 1) {
nonRepeatingCount++;
if (nonRepeatingCount === k) {
// When the count of non-repeating characters equals k,
// return the character
return char;
}
}
}
// If there is no kth non-repeating character in the string,
// return the null character
return '\0';
}
// Main function
function main() {
const str = "w3wiki";
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(n)
This article is contributed by Aarti_Rathi and Shivam Gupta.
K’th Non-repeating Character
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 = w3wiki, k = 3
Output : r
Explanation: First non-repeating character is f, second is o and third is r.Input : str = w3wiki, k = 2
Output : oInput : str = w3wiki, k = 4
Output : Less than k non-repeating characters in input.
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
This problem is mainly an extension of the First non-repeating character problem.