Skip to main content

Kth non repeating character in a string

The Kth non-repeating character in a string is the Kth character that appears only once in the string. In other words, it is the Kth character from the left of the string that has no repeated occurrences to its left.

Here's how we can find the Kth non-repeating character in a string:

  1. Traverse the string character by character and count the frequency of each character.
  2. Traverse the string again and for each character, check if its frequency is equal to K.
  3. If the frequency of a character is equal to K, return that character as it is the Kth non-repeating character in the string.
  4. If no character has a frequency equal to K, return -1 to indicate that there is no Kth non-repeating character in the string.

Using the string "atrbeaace" as an example, we can follow these steps:

Character	Frequency
a	         3
t	         1
b	         1
e            2
c	         1

  1. The first non-repeating character is 't', which appears only once and is not repeated before or after its occurrence.
  2. The second non-repeating character is 'b', which also appears only once and is not repeated before or after its occurrence.
  3. The third non-repeating character is 'c', which appears only once and is not repeated before or after its occurrence.

Here given code implementation process.

/*
  Java program for
  Kth non repeating character in a string
*/
public class Alphabets
{
	public void kthNonRepeatChar(String text, int k)
	{
		int n = text.length();
		if (n == 0 || k <= 0 || k > n)
		{
			return;
		}
		System.out.println(" Given Text : " + text);
		// Use to collect frequency of character
		int[] record = new int[256];
		int count = 0;
		// Set initial frequency of character
		for (int i = 0; i < 256; ++i)
		{
			record[i] = 0;
		}
		// Count character frequency
		for (int i = 0; i < n; ++i)
		{
			record[text.charAt(i)] += 1;
		}
		// Find kth non repeating character
		// From left to right
		for (int i = 0; i < n; ++i)
		{
			if (record[text.charAt(i)] == 1)
			{
				count++;
				if (count == k)
				{
					System.out.println(" " + k + 
                                       "'th non character is : " +
                                       text.charAt(i));
					return;
				}
			}
		}
		// When kth non repeating character not exist in given text
		System.out.print(" " + k + 
                         "-th non repeating character is not exist\n");
	}
	public static void main(String[] args)
	{
		Alphabets task = new Alphabets();
		/*
		    Case A
		    ------
		    G o o g l e P l a y G a m e 
		          -     -     -     -      
		          ①    ②    ③     ④
		*/
		task.kthNonRepeatChar("GooglePlayGame", 3);
		/*
		    Case B
		    ------
		    1  2  3  4   7   3   9   0   3  2
		    -        -   -       -   -  
		    ①       ②  ③       ④  ⑤
		*/
		task.kthNonRepeatChar("1234739032", 5);
	}
}

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
  C++ program for
  Kth non repeating character in a string
*/
class Alphabets
{
	public: void kthNonRepeatChar(string text, int k)
	{
		int n = text.length();
		if (n == 0 || k <= 0 || k > n)
		{
			return;
		}
		cout << " Given Text : " << text << endl;
		// Use to collect frequency of character
		int record[256];
		int count = 0;
		// Set initial frequency of character
		for (int i = 0; i < 256; ++i)
		{
			record[i] = 0;
		}
		// Count character frequency
		for (int i = 0; i < n; ++i)
		{
			record[text[i]] += 1;
		}
		// Find kth non repeating character
		// From left to right
		for (int i = 0; i < n; ++i)
		{
			if (record[text[i]] == 1)
			{
				count++;
				if (count == k)
				{
					cout << " " << k 
                  		 << "\'th non character is : "
                         << text[i] 
                         << endl;
					return;
				}
			}
		}
		// When kth non repeating character not exist in given text
		cout << " " 
             << k 
             << "-th non repeating character is not exist\n";
	}
};
int main()
{
	Alphabets *task = new Alphabets();
	/*
	    Case A
	    ------
	    G o o g l e P l a y G a m e 
	          -     -     -     -      
	          ①    ②    ③     ④
	*/
	task->kthNonRepeatChar("GooglePlayGame", 3);
	/*
	    Case B
	    ------
	    1  2  3  4   7   3   9   0   3  2
	    -        -   -       -   -  
	    ①       ②  ③       ④  ⑤
	*/
	task->kthNonRepeatChar("1234739032", 5);
	return 0;
}

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
// Include namespace system
using System;
/*
  Csharp program for
  Kth non repeating character in a string
*/
public class Alphabets
{
	public void kthNonRepeatChar(String text, int k)
	{
		int n = text.Length;
		if (n == 0 || k <= 0 || k > n)
		{
			return;
		}
		Console.WriteLine(" Given Text : " + text);
		// Use to collect frequency of character
		int[] record = new int[256];
		int count = 0;
		// Set initial frequency of character
		for (int i = 0; i < 256; ++i)
		{
			record[i] = 0;
		}
		// Count character frequency
		for (int i = 0; i < n; ++i)
		{
			record[text[i]] += 1;
		}
		// Find kth non repeating character
		// From left to right
		for (int i = 0; i < n; ++i)
		{
			if (record[text[i]] == 1)
			{
				count++;
				if (count == k)
				{
					Console.WriteLine(" " + k + 
                                      "\'th non character is : " +
                                      text[i]);
					return;
				}
			}
		}
		// When kth non repeating character not exist in given text
		Console.Write(" " + k + 
                      "-th non repeating character is not exist\n");
	}
	public static void Main(String[] args)
	{
		Alphabets task = new Alphabets();
		/*
		    Case A
		    ------
		    G o o g l e P l a y G a m e 
		          -     -     -     -      
		          ①    ②    ③     ④
		*/
		task.kthNonRepeatChar("GooglePlayGame", 3);
		/*
		    Case B
		    ------
		    1  2  3  4   7   3   9   0   3  2
		    -        -   -       -   -  
		    ①       ②   ③      ④   ⑤
		*/
		task.kthNonRepeatChar("1234739032", 5);
	}
}

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
package main
import "fmt"
/*
  Go program for
  Kth non repeating character in a string
*/

func kthNonRepeatChar(text string, k int) {
	var n int = len(text)
	if n == 0 || k <= 0 || k > n {
		return
	}
	fmt.Println(" Given Text : ", text)
	// Use to collect frequency of character
	var record = make([] int,256)
	var count int = 0
	// Set initial frequency of character
	for i := 0 ; i < 256 ; i++ {
		record[i] = 0
	}
	// Count character frequency
	for i := 0 ; i < n ; i++ {
		record[text[i]] += 1
	}
	// Find kth non repeating character
	// From left to right
	for i := 0 ; i < n ; i++ {
		if record[text[i]] == 1 {
			count++
			if count == k {
				fmt.Printf(" %d'th non character is : %c\n",k, text[i])
				return
			}
		}
	}
	// When kth non repeating character not exist in given text
	fmt.Print(" ", k, "-th non repeating character is not exist\n")
}
func main() {

	/*
	    Case A
	    ------
	    G o o g l e P l a y G a m e 
	          -     -     -     -      
	          ①    ②    ③     ④
	*/
	kthNonRepeatChar("GooglePlayGame", 3)
	/*
	    Case B
	    ------
	    1  2  3  4   7   3   9   0   3  2
	    -        -   -       -   -  
	    ①       ②   ③      ④   ⑤
	*/
	kthNonRepeatChar("1234739032", 5)
}

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
<?php
/*
  Php program for
  Kth non repeating character in a string
*/
class Alphabets
{
	public	function kthNonRepeatChar($text, $k)
	{
		$n = strlen($text);
		if ($n == 0 || $k <= 0 || $k > $n)
		{
			return;
		}
		echo(" Given Text : ".$text."\n");
		// Use to collect frequency of character
		// Set initial 0 frequency to possible character 0..256
		$record = array_fill(0, 256, 0);
		$count = 0;
		// Count character frequency
		for ($i = 0; $i < $n; ++$i)
		{
			$record[ord($text[$i])] += 1;
		}
		// Find kth non repeating character
		// From left to right
		for ($i = 0; $i < $n; ++$i)
		{
			if ($record[ord($text[$i])] == 1)
			{
				$count++;
				if ($count == $k)
				{
					echo(" ".$k.
						"'th non character is : ".$text[$i].
						"\n");
					return;
				}
			}
		}
		// When kth non repeating character not exist in given text
		echo(" ".$k."-th non repeating character is not exist\n");
	}
}

function main()
{
	$task = new Alphabets();
	/*
	    Case A
	    ------
	    G o o g l e P l a y G a m e 
	          -     -     -     -      
	          ①    ②    ③     ④
	*/
	$task->kthNonRepeatChar("GooglePlayGame", 3);
	/*
	    Case B
	    ------
	    1  2  3  4   7   3   9   0   3  2
	    -        -   -       -   -  
	    ①       ②  ③       ④  ⑤
	*/
	$task->kthNonRepeatChar("1234739032", 5);
}
main();

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
/*
  Node JS program for
  Kth non repeating character in a string
*/
class Alphabets
{
	kthNonRepeatChar(text, k)
	{
		var n = text.length;
		if (n == 0 || k <= 0 || k > n)
		{
			return;
		}
		console.log(" Given Text : " + text);
		// Use to collect frequency of character
		// Set initial 0 frequency to possible character 0..256
		var record = Array(256).fill(0);
		var count = 0;
		// Count character frequency
		for (var i = 0; i < n; ++i)
		{
			record[text.charCodeAt(i)] += 1;
		}
		// Find kth non repeating character
		// From left to right
		for (var i = 0; i < n; ++i)
		{
			if (record[text.charCodeAt(i)] == 1)
			{
				count++;
				if (count == k)
				{
					console.log(" " + k + 
                                "'th non character is : " + text.charAt(i));
					return;
				}
			}
		}
		// When kth non repeating character not exist in given text
		process.stdout.write(" " + k + 
                             "-th non repeating character is not exist\n");
	}
}

function main()
{
	var task = new Alphabets();
	/*
	    Case A
	    ------
	    G o o g l e P l a y G a m e 
	          -     -     -     -      
	          ①    ②    ③     ④
	*/
	task.kthNonRepeatChar("GooglePlayGame", 3);
	/*
	    Case B
	    ------
	    1  2  3  4   7   3   9   0   3  2
	    -        -   -       -   -  
	    ①       ②  ③       ④  ⑤
	*/
	task.kthNonRepeatChar("1234739032", 5);
}
main();

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
#  Python 3 program for
#  Kth non repeating character in a string
class Alphabets :
	def kthNonRepeatChar(self, text, k) :
		n = len(text)
		if (n == 0 or k <= 0 or k > n) :
			return
		
		print(" Given Text : ", text)
		#  Use to collect frequency of character
		#  Set initial 0 frequency to possible character 0..256
		record = [0] * (256)
		count = 0
		i = 0
		#  Count character frequency
		while (i < n) :
			record[ord(text[i])] += 1
			i += 1
		
		i = 0
		#  Find kth non repeating character
		#  From left to right
		while (i < n) :
			if (record[ord(text[i])] == 1) :
				count += 1
				if (count == k) :
					print(" ", k ,"'th non character is : ", text[i],sep="")
					return
				
			
			i += 1
		
		#  When kth non repeating character not exist in given text
		print(" ", k ,"-th non repeating character is not exist")
	

def main() :
	task = Alphabets()
	#    Case A
	#    ------
	#    G o o g l e P l a y G a m e 
	#          -     -     -     -      
	#          ①    ②    ③     ④
	task.kthNonRepeatChar("GooglePlayGame", 3)
	#    Case B
	#    ------
	#    1  2  3  4   7   3   9   0   3  2
	#    -        -   -       -   -  
	#    ①       ②  ③       ④  ⑤
	task.kthNonRepeatChar("1234739032", 5)

if __name__ == "__main__": main()

Output

 Given Text :  GooglePlayGame
 3'th non character is : y
 Given Text :  1234739032
 5'th non character is : 0
#  Ruby program for
#  Kth non repeating character in a string
class Alphabets 
	def kthNonRepeatChar(text, k) 
		n = text.length
		if (n == 0 || k <= 0 || k > n) 
			return
		end

		print(" Given Text : ", text, "\n")
		#  Use to collect frequency of character
		#  Set initial 0 frequency to possible character 0..256
		record = Array.new(256) {0}
		count = 0
		i = 0
		#  Count character frequency
		while (i < n) 
			record[text[i].ord] += 1
			i += 1
		end

		i = 0
		#  Find kth non repeating character
		#  From left to right
		while (i < n) 
			if (record[text[i].ord] == 1) 
				count += 1
				if (count == k) 
					print(" ", k ,"'th non character is : ", text[i], "\n")
					return
				end

			end

			i += 1
		end

		#  When kth non repeating character not exist in given text
		print(" ", k ,"-th non repeating character is not exist\n")
	end

end

def main() 
	task = Alphabets.new()
	#    Case A
	#    ------
	#    G o o g l e P l a y G a m e 
	#          -     -     -     -      
	#          ①    ②     ③    ④
	task.kthNonRepeatChar("GooglePlayGame", 3)
	#    Case B
	#    ------
	#    1  2  3  4   7   3   9   0   3  2
	#    -        -   -       -   -  
	#    ①       ②   ③      ④   ⑤
	task.kthNonRepeatChar("1234739032", 5)
end

main()

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0

import scala.collection.mutable._;
/*
  Scala program for
  Kth non repeating character in a string
*/
class Alphabets()
{
	def kthNonRepeatChar(text: String, k: Int): Unit = {
		var n: Int = text.length();
		if (n == 0 || k <= 0 || k > n)
		{
			return;
		}
		println(" Given Text : " + text);
		// Use to collect frequency of character
		// Set initial 0 frequency to possible character 0..256
		var record: Array[Int] = Array.fill[Int](256)(0);
		var count: Int = 0;
		var i: Int = 0;
		// Count character frequency
		while (i < n)
		{
			record(text.charAt(i)) += 1;
			i += 1;
		}
		i = 0;
		// Find kth non repeating character
		// From left to right
		while (i < n)
		{
			if (record(text.charAt(i)) == 1)
			{
				count += 1;
				if (count == k)
				{
					println(" " + k + "\'th non character is : " + 
                            text.charAt(i));
					return;
				}
			}
			i += 1;
		}
		// When kth non repeating character not exist in given text
		print(" " + k + "-th non repeating character is not exist\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Alphabets = new Alphabets();
		/*
		    Case A
		    ------
		    G o o g l e P l a y G a m e 
		          -     -     -     -      
		          ①    ②    ③     ④
		*/
		task.kthNonRepeatChar("GooglePlayGame", 3);
		/*
		    Case B
		    ------
		    1  2  3  4   7   3   9   0   3  2
		    -        -   -       -   -  
		    ①       ②  ③       ④  ⑤
		*/
		task.kthNonRepeatChar("1234739032", 5);
	}
}

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
import Foundation;
/*
  Swift 4 program for
  Kth non repeating character in a string
*/
class Alphabets
{
	func kthNonRepeatChar(_ data: String, _ k: Int)
	{
		let n: Int = data.count;
		if (n == 0 || k <= 0 || k > n)
		{
			return;
		}
		print(" Given Text : ", data);
		// Use to collect frequency of character
		// Set initial 0 frequency to possible character 0..256
		var record: [Int] = Array(repeating: 0, count: 256);
		var count: Int = 0;
		var i: Int = 0;
      	var j = 0;
      	let text = Array(data);
		// Count character frequency
		while (i < n)
		{
          	j = Int(UnicodeScalar(String(text[i]))!.value);
			record[j] += 1;
			i += 1;
		}
		i = 0;
		// Find kth non repeating character
		// From left to right
		while (i < n)
		{
          	j = Int(UnicodeScalar(String(text[i]))!.value);
			if (record[j] == 1)
			{
				count += 1;
				if (count == k)
				{
					print(" ", k ,"\'th non character is : ", text[i]);
					return;
				}
			}
			i += 1;
		}
		// When kth non repeating character not exist in given text
		print(" ", k ,"-th non repeating character is not exist");
	}
}
func main()
{
	let task: Alphabets = Alphabets();
	/*
	    Case A
	    ------
	    G o o g l e P l a y G a m e 
	          -     -     -     -      
	          ①    ②    ③     ④
	*/
	task.kthNonRepeatChar("GooglePlayGame", 3);
	/*
	    Case B
	    ------
	    1  2  3  4   7   3   9   0   3  2
	    -        -   -       -   -  
	    ①       ②  ③       ④  ⑤
	*/
	task.kthNonRepeatChar("1234739032", 5);
}
main();

Output

 Given Text :  GooglePlayGame
  3 'th non character is :  y
 Given Text :  1234739032
  5 'th non character is :  0
/*
  Kotlin program for
  Kth non repeating character in a string
*/
class Alphabets
{
	fun kthNonRepeatChar(text: String, k: Int): Unit
	{
		val n: Int = text.length;
		if (n == 0 || k <= 0 || k > n)
		{
			return;
		}
		println(" Given Text : " + text);
		// Use to collect frequency of character
		// Set initial 0 frequency to possible character 0..256
		val record: Array < Int > = Array(256)
		{
			0
		};
		var count: Int = 0;
		var i: Int = 0;
		// Count character frequency
		while (i < n)
		{
			record[text.get(i).toInt()] += 1;
			i += 1;
		}
		i = 0;
		// Find kth non repeating character
		// From left to right
		while (i < n)
		{
			if (record[text.get(i).toInt()] == 1)
			{
				count += 1;
				if (count == k)
				{
					println(" " + k + "\'th non character is : " + text.get(i));
					return;
				}
			}
			i += 1;
		}
		// When kth non repeating character not exist in given text
		print(" " + k + "-th non repeating character is not exist\n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Alphabets = Alphabets();
	/*
	    Case A
	    ------
	    G o o g l e P l a y G a m e 
	          -     -     -     -      
	          ①    ②    ③     ④
	*/
	task.kthNonRepeatChar("GooglePlayGame", 3);
	/*
	    Case B
	    ------
	    1  2  3  4   7   3   9   0   3  2
	    -        -   -       -   -  
	    ①       ②  ③       ④  ⑤
	*/
	task.kthNonRepeatChar("1234739032", 5);
}

Output

 Given Text : GooglePlayGame
 3'th non character is : y
 Given Text : 1234739032
 5'th non character is : 0
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment