JavaScript Program to Find K’th Non-Repeating Character in String
Last Updated :
09 Jul, 2024
The K'th non-repeating character in a string is found by iterating through the string length and counting how many times each character has appeared. When any character is found that appears only once and it is the K'th unique character encountered, it is returned as the result. This operation helps identify the K'th non-repeating character in the string. In this article, we will find K’th Non-repeating Character in a string using JavaScript.
Examples :
Input: s = 'geeksforgeeks' , K = 2
Output: o
Explanation: In the given string, the 2nd non-repeating character is 'o' because 'f' is the first
character that appears only once and 'o' is the next character following it.
Input: 'javascript', K = 4
Output: c
Explanation: In the given string, the 4th non-repeating character is 'c' as 'j', 'v', and 's' are the characters
that appears only once and 'c' is the next character following it.
Method 1: Brute Force approach
As a brute force solution, use nested loops to traverse through the string. Starting from the first element, check for every character whether it repeats or not. Use a counter to keep a count of unique elements. When the count reaches K, return the character.
Algorithm:
- Iterate the string from left character by character.
- For each element in the outer loop, keep a check if the character is repeating in the inner loop.
- Initialize a flag to check for the repeating character.
- If the character does not repeat, increment the counter.
- Whenever the count reaches K, return the current character as our answer.
- If Kth non-repeating character is not found, return null which indicates that the character does not exist.
Example: In this code we will find K’th Non-repeating Character in string with brute force approach.
JavaScript
function kthNonRepeating(s, K) {
const n = s.length;
let cnt = 0, ans = null;
for (let i = 0; i < n; i++) {
let flag = 0;
for (let j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
flag = 1;
break;
}
}
if (!flag) {
cnt++;
if (cnt == K) {
ans = s[i];
break;
}
}
}
return ans;
}
let s = "geeksforgeeks";
let K = 3;
let res = kthNonRepeating(s, K);
if (res == null) {
console.log(-1);
}
else {
console.log(res);
}
Time Complexity: O(N2)
Auxiliary Space: O(1)
Method 2: Using Hashmap
Store the character frequency in a hashmap. Then iterate through the string an find the appropriate character whose frequency is 1 and return the Kth element.
Algorithm:
- Create a map to store the count of the characters.
- Iterate through the string and update their frequencies respectively.
- Again traverse through the string.
- If frequency of the character is 1, decrement the value of K.
- Once the value of K reaches 0, return the current character.
Example: In this code we will find K’th Non-repeating Character in string by using hashmap approach.
JavaScript
function KthNonRepeatingChar(s, K) {
const n = s.length;
// Create a map
let mp = {};
let ans = null;
// Iterate through the string
for (let i = 0; i < n; i++) {
let ch = s[i];
if (mp[ch] == undefined) {
mp[ch] = 1;
}
else {
mp[ch]++;
}
}
// Iterate through the string again
// and find the Kth non-repeating character
for (let i = 0; i < n; i++) {
let ch = s[i];
if (mp[ch] == 1) {
K--;
if (K == 0) {
ans = ch;
}
}
}
return ans;
}
let s = "geeksforgeeks";
const K = 3;
// Function call
let ans = KthNonRepeatingChar(s, K);
console.log(ans);
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 3: Using Map
This approach employs a Map data structure to efficiently count the occurrences of each character in the string. By utilizing a map, we can achieve a linear time complexity solution.
Algorithm:
- Create a
Map to store the count of occurrences of each character in the string. - Iterate through the string, updating the counts in the map accordingly.
- Traverse the string again, checking for the K'th non-repeating character based on the counts stored in the map.
- If the K'th non-repeating character is found, return it; otherwise, return
null.
Example:
JavaScript
function findKthNonRepeating(s, K) {
const charCounts = new Map();
// Count occurrences of each character
for (const char of s) {
charCounts.set(char, (charCounts.get(char) || 0) + 1);
}
// Find the K'th non-repeating character
let count = 0;
for (const char of s) {
if (charCounts.get(char) === 1) {
count++;
if (count === K) {
return char;
}
}
}
// If K'th non-repeating character not found, return null
return null;
}
const s = "geeksforgeeks";
const K = 3;
const result = findKthNonRepeating(s, K);
console.log(result); // Output: r
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 4: Using Queue
This approach utilizes a queue to keep track of the order of characters as they appear and their frequency. This method leverages the properties of a queue (FIFO) to efficiently find the K'th non-repeating character.
Algorithm:
- Create a frequency map to store the count of each character.
- Create a queue to keep track of characters and their positions in the string.
- Traverse the string and update the frequency map and queue.
- Process the queue to find the K'th non-repeating character.
Here’s the implementation in JavaScript:
JavaScript
function findKthNonRepeatingUsingQueue(s, K) {
const freqMap = new Map();
const queue = [];
// Populate the frequency map and queue
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (!freqMap.has(char)) {
freqMap.set(char, 1);
queue.push(char);
} else {
freqMap.set(char, freqMap.get(char) + 1);
}
}
// Process the queue to find the K'th non-repeating character
let count = 0;
while (queue.length > 0) {
const char = queue.shift();
if (freqMap.get(char) === 1) {
count++;
if (count === K) {
return char;
}
}
}
// If K'th non-repeating character not found, return null
return null;
}
const s = "geeksforgeeks";
const K = 3;
const result = findKthNonRepeatingUsingQueue(s, K);
console.log(result); // Output: r
Method 5: Using an Array to Track Indexes
In this approach, we use an array to track the first index of each character that appears exactly once in the string. We then sort this array by indexes and select the K'th non-repeating character based on the sorted order.
Example: This example demonstrates the use of the above-explained approach.
JavaScript
function findKthNonRepeatingChar(str, K) {
const charCount = new Map();
const charIndex = new Map();
// Populate the frequency map and the index map
for (let i = 0; i < str.length; i++) {
const char = str[i];
if (charCount.has(char)) {
charCount.set(char, charCount.get(char) + 1);
} else {
charCount.set(char, 1);
charIndex.set(char, i);
}
}
// Filter characters that appear exactly once and store their indexes
const uniqueChars = [];
for (const [char, count] of charCount) {
if (count === 1) {
uniqueChars.push({char, index: charIndex.get(char)});
}
}
// Sort the characters by their first appearance index
uniqueChars.sort((a, b) => a.index - b.index);
// Return the K'th non-repeating character if it exists
return (K <= uniqueChars.length) ? uniqueChars[K - 1].char : null;
}
// Test cases
console.log(findKthNonRepeatingChar('geeksforgeeks', 2)); // Output: 'o'
console.log(findKthNonRepeatingChar('javascript', 4)); // Output: 'c'
console.log(findKthNonRepeatingChar('aabbcc', 1)); // Output: null
Similar Reads
JavaScript Program to Get a Non-Repeating Character From the Given String
In JavaScript, we can find the non-repeating character from the input string by identifying the characters that occur only once in the string. There are several approaches in JavaScript to get a non-repeating character from the given string which are as follows: Table of Content Using indexOf and la
3 min read
JavaScript Program to Check for Repeated Characters in a String
Here are the different methods to check for repeated characters in a string using JavaScript 1. Using a Frequency Counter (Object)A frequency counter is one of the most efficient ways to check for repeated characters in a string. This approach involves iterating over the string and counting how ofte
3 min read
JavaScript Program to Print All Duplicate Characters in a String
In this article, we will learn how to print all duplicate characters in a string in JavaScript. Given a string S, the task is to print all the duplicate characters with their occurrences in the given string. Example: Input: S = “geeksforgeeksâ€Output:e, count = 4g, count = 2k, count = 2s, count = 2Ta
5 min read
JavaScript Program to Remove Consecutive Duplicate Characters From a String
We are going to implement a JavaScript program to remove consecutive duplicate characters from a string. In this program, we will eliminate all the consecutive occurrences of the same character from a string. Example: Input: string: "geeks" Output: "geks"Explanation :consecutive "e" should be remove
5 min read
Javascript Program To Find Length Of The Longest Substring Without Repeating Characters
Given a string str, find the length of the longest substring without repeating characters. For “ABDEFGABEFâ€, the longest substring are “BDEFGA†and "DEFGAB", with length 6.For “BBBB†the longest substring is “Bâ€, with length 1.For "GEEKSFORGEEKS", there are two longest substrings shown in the below
5 min read
Java Program to Iterate Over Characters in String
Given string str of length N, the task is to traverse the string and print all the characters of the given string using java. Illustration: Input : str = “GeeksforGeeks†Output : G e e k s f o r G e e k sInput : str = "GfG" Output : G f G Methods: Using for loops(Naive approach)Using iterators (Opti
3 min read
Count K-Length Substrings With No Repeated Characters
Given a string S and an integer k, the task is to return the number of substrings in S of length k with no repeated characters. Example: Input: S = "geeksforgeeks", k = 5Output: 4Explanation: There are 4 substrings, they are: 'eksfo', 'ksfor', 'sforg', 'forge'. Input: S = "home", k = 5Output: 0Expla
6 min read
PHP Program to Print All Duplicate Characters in a String
This article will show you how to print duplicate characters in a string using PHP. Detecting and printing duplicate characters in a string is a common task in programming. In this article, we will explore various approaches to achieve this. Table of Content Using array_count_values() FunctionUsing
3 min read
String Class repeat() Method in Java with Examples
The string can be repeated N number of times, and we can generate a new string that has repetitions. repeat() method is used to return String whose value is the concatenation of given String repeated count times. If the string is empty or the count is zero then the empty string is returned. Syntax:
2 min read
How to remove duplicate characters from a String in Scala?
In this article, we will learn how to remove duplicate characters from a string in Scala using different approaches. First, we will look through the Brute-Force Approach and then use different standard libraries. Examples: Input: String = "hello"Output: helo Input: String = "Geeks"Output: Geks Naive
4 min read