Skip to main content

Count of substrings of length K with exactly K distinct characters

Here given code implementation process.

// Java Program 
// Count of substrings of length K with exactly K distinct characters
import java.util.HashMap;
public class Palindrome
{
	// Count all distinct k character of k length
	public void countDistinctK(String text, int k)
	{
		int count = 0;
		// Display calculated result
		System.out.print(" Given Text : " + text);
		System.out.print("\n K : " + k);
		if (k < text.length())
		{
			// Define loop controlling variable i
			int i = 0;
			// Use to count character frequency
			HashMap < Character, Integer > record = new HashMap < Character, Integer > ();
			// Find the initials K character frequency
			for (i = 0; i < k; i++)
			{
				if (record.containsKey(text.charAt(i)))
				{
					// increase character frequency
					record.put(text.charAt(i), record.get(text.charAt(i)) + 1);
				}
				else
				{
					// add new character
					record.put(text.charAt(i), 1);
				}
			}
			if (record.size() == k)
			{
				System.out.print("\n(" + text.substring(0, k) + ")");
				// Initials character are distinct
				count = 1;
			}
			for (i = k; i < text.length(); i++)
			{
				if (record.containsKey(text.charAt(i)))
				{
					// increase character frequency
					record.put(text.charAt(i), record.get(text.charAt(i)) + 1);
				}
				else
				{
					// add new character
					record.put(text.charAt(i), 1);
				}
				if (record.get(text.charAt(i - k)) > 1)
				{
					// Reduce the (i - k) - th character frequency
					// Reduce character frequency
					record.put(text.charAt(i - k), record.get(text.charAt(i - k)) - 1);
				}
				else
				{
					// When (i - k) - th character frequency is one then remove
					record.remove(text.charAt(i - k));
				}
				if (record.size() == k)
				{
					System.out.print("\n(" + text.substring(i - k + 1, i + 1) + ")");
					// When record size equal to k
					// increase resultant counter
					count++;
				}
			}
		}
		System.out.print("\n Result : " + count);
	}
	public static void main(String[] args)
	{
		Palindrome task = new Palindrome();
		String text = "KFGTFTITCSGRROUPT";
		int k = 4;
		// KFGTFTITCSGRROUP
		// All K characters resultant pair is
		// ((KFGT)
		// (ITCS)
		// (TCSG)
		// (CSGR)
		// (ROUP)
		// (OUPT)
		task.countDistinctK(text, k);
	}
}

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
// Include header file
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

// C++ Program
// Count of substrings of length K with exactly K distinct characters

class Palindrome
{
	public:
		// Count all distinct k character of k length
		void countDistinctK(string text, int k)
		{
			int count = 0;
			// Display calculated result
			cout << " Given Text : " << text;
			cout << "\n K : " << k;
			if (k < text.length())
			{
				// Define loop controlling variable i
				int i = 0;
				// Use to count character frequency
				unordered_map < char, int > record ;
				// Find the initials K character frequency
				for (i = 0; i < k; i++)
				{
					if (record.find(text[i]) != record.end())
					{
						// increase character frequency
						record[text[i]] = record[text[i]] + 1;
					}
					else
					{
						// add new character
						record[text[i]] = 1;
					}
				}
				if (record.size() == k)
				{
					cout << "\n(" << text.substr(0, k) << ")";
					// Initials character are distinct
					count = 1;
				}
				for (i = k; i < text.length(); i++)
				{
					if (record.find(text[i]) != record.end())
					{
						// increase character frequency
						record[text[i]] = record[text[i]] + 1;
					}
					else
					{
						// add new character
						record[text[i]] = 1;
					}
					if (record[text[i - k]] > 1)
					{
						// Reduce the (i - k) - th character frequency
						// Reduce character frequency
						record[text[i - k]] = record[text[i - k]] - 1;
					}
					else
					{
						// When (i - k) - th character frequency is one then remove
						record.erase(text[i - k]);
					}
					if (record.size() == k)
					{
						// When record size equal to k
						// increase resultant counter
						cout << "\n(" << text.substr(i - k + 1, k) << ")";
						count++;
					}
				}
			}
			cout << "\n Result : " << count;
		}
};
int main()
{
	Palindrome task = Palindrome();
	string text = "KFGTFTITCSGRROUPT";
	int k = 4;
	// KFGTFTITCSGRROUP
	// All K characters resultant pair is
	// ((KFGT)
	// (ITCS)
	// (TCSG)
	// (CSGR)
	// (ROUP)
	// (OUPT)
	task.countDistinctK(text, k);
	return 0;
}

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
// Include namespace system
using System;
using System.Collections.Generic;
// C# Program
// Count of substrings of length K with exactly K distinct characters
public class Palindrome
{
	// Count all distinct k character of k length
	public void countDistinctK(String text, int k)
	{
		int count = 0;
		// Display calculated result
		Console.Write(" Given Text : " + text);
		Console.Write("\n K : " + k);
		if (k < text.Length)
		{
			// Define loop controlling variable i
			int i = 0;
			// Use to count character frequency
			Dictionary < char, int > record = new Dictionary < char, int > ();
			// Find the initials K character frequency
			for (i = 0; i < k; i++)
			{
				if (record.ContainsKey(text[i]))
				{
					// increase character frequency
					record.Add(text[i], record[text[i]] + 1);
				}
				else
				{
					// add new character
					record.Add(text[i], 1);
				}
			}
			if (record.Count == k)
			{
				Console.Write("\n(" + text.Substring(0, k) + ")");
				// Initials character are distinct
				count = 1;
			}
			for (i = k; i < text.Length; i++)
			{
				if (record.ContainsKey(text[i]))
				{
					// increase character frequency
					record[text[i]] = record[text[i]] + 1;
				}
				else
				{
					// add new character
					record.Add(text[i], 1);
				}
				if (record[text[i - k]] > 1)
				{
					// Reduce the (i - k) - th character frequency
					// Reduce character frequency
					record[text[i - k]] =  record[text[i - k]] - 1;
				}
				else
				{
					// When (i - k) - th character frequency is one then remove
					record.Remove(text[i - k]);
				}
				if (record.Count == k)
				{
					// When record size equal to k
					// increase resultant counter
					Console.Write("\n(" + text.Substring(i - k + 1, k) + ")");
					count++;
				}
			}
		}
		Console.Write("\n Result : " + count);
	}
	public static void Main(String[] args)
	{
		Palindrome task = new Palindrome();
		String text = "KFGTFTITCSGRROUPT";
		int k = 4;
		// KFGTFTITCSGRROUP
		// All K characters resultant pair is
		// ((KFGT)
		// (ITCS)
		// (TCSG)
		// (CSGR)
		// (ROUP)
		// (OUPT)
		task.countDistinctK(text, k);
	}
}

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
<?php
// Php Program
// Count of substrings of length K with exactly K distinct characters
class Palindrome
{
	// Count all distinct k character of k length
	public	function countDistinctK($text, $k)
	{
		$count = 0;
		// Display calculated result
		echo " Given Text : ". $text;
		echo "\n K : ". $k;
		if ($k < strlen($text))
		{
			// Define loop controlling variable i
			$i = 0;
			// Use to count character frequency
			 $record = array();
			// Find the initials K character frequency
			for ($i = 0; $i < $k; $i++)
			{
				if (array_key_exists($text[$i], $record))
				{ // increase character frequency
					$record[$text[$i]] = $record[$text[$i]] + 1;
				}
				else
				{ // add new character
					$record[$text[$i]] = 1;
				}
			}
			if (count($record) == $k)
			{
				echo "\n(". substr($text, 0, $k).")";
				// Initials character are distinct
				$count = 1;
			}
			for ($i = $k; $i < strlen($text); $i++)
			{
				if (array_key_exists($text[$i], $record))
				{ // increase character frequency
					$record[$text[$i]] = $record[$text[$i]] + 1;
				}
				else
				{ // add new character
					$record[$text[$i]] = 1;
				}
				if ($record[$text[$i - $k]] > 1)
				{ // Reduce the (i - k) - th character frequency
					// Reduce character frequency
					$record[$text[$i - $k]] = $record[$text[$i - $k]] - 1;
				}
				else
				{
					unset( // When (i - k) - th character frequency is one then remove
						$record[$text[$i - $k]]);
				}
				if (count($record) == $k)
				{
					// When record size equal to k
					// increase resultant counter
					echo "\n(". substr($text, $i - $k + 1, $k) .")";
					$count++;
				}
			}
		}
		echo "\n Result : ". $count;
	}
}

function main()
{
	$task = new Palindrome();
	$text = "KFGTFTITCSGRROUPT";
	$k = 4;
	$task->countDistinctK($text, $k);
}
main();

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
// Node Js Program
// Count of substrings of length K with exactly K distinct characters
class Palindrome
{
	// Count all distinct k character of k length
	countDistinctK(text, k)
	{
		var count = 0;
		// Display calculated result
		process.stdout.write(" Given Text : " + text);
		process.stdout.write("\n K : " + k);
		if (k < text.length)
		{
			// Define loop controlling variable i
			var i = 0;
			// Use to count character frequency
			var record = new Map();
			// Find the initials K character frequency
			for (i = 0; i < k; i++)
			{
				if (record.has(text.charAt(i)))
				{
					// increase character frequency
					record.set(text.charAt(i), record.get(text.charAt(i)) + 1);
				}
				else
				{
					// add new character
					record.set(text.charAt(i), 1);
				}
			}
			if (record.size == k)
			{
				process.stdout.write("\n(" + text.substring(0, k) + ")");
				// Initials character are distinct
				count = 1;
			}
			for (i = k; i < text.length; i++)
			{
				if (record.has(text.charAt(i)))
				{
					// increase character frequency
					record.set(text.charAt(i), record.get(text.charAt(i)) + 1);
				}
				else
				{
					// add new character
					record.set(text.charAt(i), 1);
				}
				if (record.get(text.charAt(i - k)) > 1)
				{
					// Reduce the (i - k) - th character frequency
					// Reduce character frequency
					record.set(text.charAt(i - k), record.get(text.charAt(i - k)) - 1);
				}
				else
				{
					// When (i - k) - th character frequency is one then remove
					record.delete(text.charAt(i - k));
				}
				if (record.size == k)
				{
					// When record size equal to k
					// increase resultant counter
					process.stdout.write("\n(" + text.substring(i - k + 1, i + 1) + ")");
					count++;
				}
			}
		}
		process.stdout.write("\n Result : " + count);
	}
}

function main()
{
	var task = new Palindrome();
	var text = "KFGTFTITCSGRROUPT";
	var k = 4;
	// KFGTFTITCSGRROUP
	// All K characters resultant pair is
	// ((KFGT)
	// (ITCS)
	// (TCSG)
	// (CSGR)
	// (ROUP)
	// (OUPT)
	task.countDistinctK(text, k);
}
main();

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
#  Python 3 Program
#  Count of substrings of length K with exactly K distinct characters
class Palindrome :
	#  Count all distinct k character of k length
	def countDistinctK(self, text, k) :
		count = 0
		#  Display calculated result
		print(" Given Text : ", text, end = "")
		print("\n K : ", k, end = "")
		if (k < len(text)) :
			#  Define loop controlling variable i
			i = 0
			#  Use to count character frequency
			record = dict()
			#  Find the initials K character frequency
			while (i < k) :
				if (text[i] in record.keys()) :
					#  increase character frequency
					record[text[i]] = record.get(text[i]) + 1
				else :
					#  add new character
					record[text[i]] = 1
				
				i += 1
			
			if (len(record) == k) :
				print("\n(", text[0: k] ,")", end = "")
				#  Initials character are distinct
				count = 1
			
			i = k
			while (i < len(text)) :
				if (text[i] in record.keys()) :
					#  increase character frequency
					record[text[i]] = record.get(text[i]) + 1
				else :
					#  add new character
					record[text[i]] = 1
				
				if (record.get(text[i - k]) > 1) :
					#  Reduce the (i - k) - th character frequency
					#  Reduce character frequency
					record[text[i - k]] = record.get(text[i - k]) - 1
				else :
					#  When (i - k) - th character frequency is one then remove
					del record[text[i - k]]
				
				if (len(record) == k) :
					#  When record size equal to k
					#  increase resultant counter
					print("\n(", text[i - k + 1: i + 1] ,")", end = "")
					count += 1
				
				i += 1
			
		
		print("\n Result : ", count, end = "")
	

def main() :
	task = Palindrome()
	text = "KFGTFTITCSGRROUPT"
	k = 4
	#  KFGTFTITCSGRROUP
	#  All K characters resultant pair is
	#  ((KFGT)
	#  (ITCS)
	#  (TCSG)
	#  (CSGR)
	#  (ROUP)
	#  (OUPT)
	task.countDistinctK(text, k)

if __name__ == "__main__": main()

Output

 Given Text :  KFGTFTITCSGRROUPT
 K :  4
( KFGT )
( ITCS )
( TCSG )
( CSGR )
( ROUP )
( OUPT )
 Result :  6
#  Ruby Program
#  Count of substrings of length K with exactly K distinct characters
class Palindrome 
	#  Count all distinct k character of k length
	def countDistinctK(text, k) 
		count = 0
		#  Display calculated result
		print(" Given Text : ", text)
		print("\n K : ", k)
		if (k < text.length) 
			#  Define loop controlling variable i
			i = 0
			#  Use to count character frequency
			record = Hash.new 
			#  Find the initials K character frequency
			while (i < k) 
				if (record.key?(text[i])) 
					record[text[i]] = record[text[i]] + 1
				else 
					record[text[i]] = 1
				end

				i += 1
			end

			if (record.size() == k) 
				print("\n(", text[0...k] ,")")
				#  Initials character are distinct
				count = 1
			end

			i = k
			while (i < text.length) 
				if (record.key?(text[i])) 
					record[text[i]] = record[text[i]] + 1
				else 
					record[text[i]] = 1
				end

				if (record[text[i - k]] > 1) 
					record[text[i - k]] = record[text[i - k]] - 1
				else 
					record.delete(text[i - k])
				end

				if (record.size() == k) 
					#  When record size equal to k
					#  increase resultant counter
					print("\n(", text[i - k + 1...i + 1] ,")")
					count += 1
				end

				i += 1
			end

		end

		print("\n Result : ", count)
	end

end

def main() 
	task = Palindrome.new()
	text = "KFGTFTITCSGRROUPT"
	k = 4
	#  KFGTFTITCSGRROUP
	#  All K characters resultant pair is
	#  ((KFGT)
	#  (ITCS)
	#  (TCSG)
	#  (CSGR)
	#  (ROUP)
	#  (OUPT)
	task.countDistinctK(text, k)
end

main()

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
import scala.collection.mutable._;
// Scala Program
// Count of substrings of length K with exactly K distinct characters
class Palindrome
{
	// Count all distinct k character of k length
	def countDistinctK(text: String, k: Int): Unit = {
		var count: Int = 0;
		// Display calculated result
		print(" Given Text : " + text);
		print("\n K : " + k);
		if (k < text.length())
		{
			// Define loop controlling variable i
			var i: Int = 0;
			// Use to count character frequency
			var record  = Map[Character, Int]();
			// Find the initials K character frequency
			while (i < k)
			{
				if (record.contains(text.charAt(i)))
				{
					// increase character frequency
					record.addOne(text.charAt(i), record.get(text.charAt(i)).get + 1);
				}
				else
				{
					// add new character
					record.addOne(text.charAt(i), 1);
				}
				i += 1;
			}
			if (record.size == k)
			{
				print("\n(" + text.substring(0, k) + ")");
				// Initials character are distinct
				count = 1;
			}
			i = k;
			while (i < text.length())
			{
				if (record.contains(text.charAt(i)))
				{
					// increase character frequency
					record.addOne(text.charAt(i), record.get(text.charAt(i)).get + 1);
				}
				else
				{
					// add new character
					record.addOne(text.charAt(i), 1);
				}
				if (record.get(text.charAt(i - k)).get > 1)
				{
					// Reduce the (i - k) - th character frequency
					// Reduce character frequency
					record.addOne(text.charAt(i - k), record.get(text.charAt(i - k)).get - 1);
				}
				else
				{
					// When (i - k) - th character frequency is one then remove
					record.remove(text.charAt(i - k));
				}
				if (record.size == k)
				{
					// When record size equal to k
					// increase resultant counter
					print("\n(" + text.substring(i - k + 1, i + 1) + ")");
					count += 1;
				}
				i += 1;
			}
		}
		print("\n Result : " + count);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Palindrome = new Palindrome();
		var text: String = "KFGTFTITCSGRROUPT";
		var k: Int = 4;
		// KFGTFTITCSGRROUP
		// All K characters resultant pair is
		// ((KFGT)
		// (ITCS)
		// (TCSG)
		// (CSGR)
		// (ROUP)
		// (OUPT)
		task.countDistinctK(text, k);
	}
}

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
// Kotlin Program
// Count of substrings of length K with exactly K distinct characters
class Palindrome
{
	// Count all distinct k character of k length
	fun countDistinctK(text: String, k: Int): Unit
	{
		var count: Int = 0;
		// Display calculated result
		print(" Given Text : " + text);
		print("\n K : " + k);
		if (k < text.length)
		{
			// Define loop controlling variable i
			var i: Int = 0;
			// Use to count character frequency
			var record = mutableMapOf < Char , Int > ();
			// Find the initials K character frequency
			while (i < k)
			{
				if (record.containsKey(text.get(i)))
				{
					// increase character frequency
					record.put(text.get(i), record.getValue(text.get(i)) + 1);
				}
				else
				{
					// add new character
					record.put(text.get(i), 1);
				}
				i += 1;
			}
			if (record.count() == k)
			{
				print("\n(" + text.subSequence(0, k) + ")").toString();
				// Initials character are distinct
				count = 1;
			}
			i = k;
			while (i < text.length)
			{
				if (record.containsKey(text.get(i)))
				{
					// increase character frequency
					record.put(text.get(i), record.getValue(text.get(i)) + 1);
				}
				else
				{
					// add new character
					record.put(text.get(i), 1);
				}
				if (record.getValue(text.get(i - k)) > 1)
				{
					// Reduce the (i - k) - th character frequency
					// Reduce character frequency
					record.put(text.get(i - k), record.getValue(text.get(i - k)) - 1);
				}
				else
				{
					// When (i - k) - th character frequency is one then remove
					record.remove(text.get(i - k));
				}
				if (record.count() == k)
				{
					// When record size equal to k
					// increase resultant counter
					print("\n(" + text.subSequence(i - k + 1, i + 1).toString() + ")");
					count += 1;
				}
				i += 1;
			}
		}
		print("\n Result : " + count);
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Palindrome = Palindrome();
	var text: String = "KFGTFTITCSGRROUPT";
	var k: Int = 4;
	// KFGTFTITCSGRROUP
	// All K characters resultant pair is
	// ((KFGT)
	// (ITCS)
	// (TCSG)
	// (CSGR)
	// (ROUP)
	// (OUPT)
	task.countDistinctK(text, k);
}

Output

 Given Text : KFGTFTITCSGRROUPT
 K : 4
(KFGT)
(ITCS)
(TCSG)
(CSGR)
(ROUP)
(OUPT)
 Result : 6
import Foundation
// Swift 4 Program
// Count of substrings of length K with exactly K distinct characters
class Palindrome
{
	// Count all distinct k character of k length
	func countDistinctK(_ t: String, _ k: Int)
	{
        var text = Array(t);
		var count: Int = 0;
		// Display calculated result
		print(" Given Text : ", t, terminator: "");
		print("\n K : ", k, terminator: "");
		if (k < text.count)
		{
			// Define loop controlling variable i
			var i: Int = 0;
			// Use to count character frequency
			var record = [Character: Int]();
			// Find the initials K character frequency
			while (i < k)
			{
				if (record.keys.contains(text[i]))
				{
					// increase character frequency
					record[text[i]] = record[text[i]]! + 1;
				}
				else
				{
					// add new character
					record[text[i]] = 1;
				}
				i += 1;
			}
			if (record.count == k)
			{
               // find index of substring
              
				print("\n(", String(text.prefix(k)) ,")", terminator: "");
				// Initials character are distinct
				count = 1;
			}
			i = k;
			while (i < text.count)
			{
				if (record.keys.contains(text[i]))
				{
					// increase character frequency
					record[text[i]] = record[text[i]]! + 1;
				}
				else
				{
					// add new character
					record[text[i]] = 1;
				}
				if (record[text[i - k]]! > 1)
				{
					// Reduce the (i - k) - th character frequency
					// Reduce character frequency
					record[text[i - k]] = record[text[i - k]]! - 1;
				}
				else
				{
					// When (i - k) - th character frequency is one then remove
					record.removeValue(forKey: text[i - k]);
				}
				if (record.count == k)
				{
                    // find index of substring
                    let range = (i - k + 1)..<( i + 1);
					// When record size equal to k
					// increase resultant counter
					print("\n(", String(text[range]) ,")", terminator: "");
					count += 1;
				}
				i += 1;
			}
		}
		print("\n Result : ", count, terminator: "");
	}
}
func main()
{
	let task: Palindrome = Palindrome();
	let text: String = "KFGTFTITCSGRROUPT";
	let k: Int = 4;
	// KFGTFTITCSGRROUP
	// All K characters resultant pair is
	// ((KFGT)
	// (ITCS)
	// (TCSG)
	// (CSGR)
	// (ROUP)
	// (OUPT)
	task.countDistinctK(text, k);
}
main();

Output

 Given Text :  KFGTFTITCSGRROUPT
 K :  4
( KFGT )
( ITCS )
( TCSG )
( CSGR )
( ROUP )
( OUPT )
 Result :  6
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