Skip to main content

Count M-length substrings occurring exactly K times in a string

Here given code implementation process.

import java.util.HashMap;
/*
    Java program for
    Count M-length substrings occurring exactly K times in a string
*/
public class Substrings
{
	public void findNlengthKoccurs(String text, int m, int k)
	{
		// Get the length of given text 
		int n = text.length();
		int result = 0;
		if (k > 0 && k < n && m > 0 && m < n)
		{
			HashMap < String, Integer > record = 
              new HashMap < String, Integer > ();
			String auxiliary = "";
			for (int i = 0; i <= n - m; ++i)
			{
				auxiliary = text.substring(i, i + m);
				if (record.containsKey(auxiliary))
				{
					// Increase frequency
					record.put(auxiliary, record.get(auxiliary) + 1);
				}
				else
				{
					// Add new key value 
					record.put(auxiliary, 1);
				}
			}
			for (String v: record.keySet())
			{
				if (record.get(v) == k)
				{
					result++;
				}
			}
		}
		if (result == 0)
		{
			System.out.print("\n None ");
		}
		else
		{
			System.out.print("\n  " + result);
		}
	}
	public static void main(String[] args)
	{
		Substrings task = new Substrings();
		String text = "itiopvitiiop";
		int m = 2;
		int k = 2;
		// Test A 
		// str = itiopvitiiop
		// m = 2 length of 2
		// k = 2 occurrence of 2
		// [op, ti,  io, it]
		// Output : 4
		task.findNlengthKoccurs(text, m, k);
		text = "xxxyyyzzztp";
		m = 3;
		k = 1;
		// Test B 
		// str = itiopvitiiop
		// m = 3 length of 3
		// k = 1 occurrence of 1
		// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
		// Output : 9
		task.findNlengthKoccurs(text, m, k);
	}
}

Output

  4
  9
// Include header file
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;
/*
    C++ program for
    Count M-length substrings occurring exactly K times in a string
*/
class Substrings
{
	public: void findNlengthKoccurs(string text, int m, int k)
	{
		// Get the length of given text 
		int n = text.length();
		int result = 0;
		if (k > 0 && k < n && m > 0 && m < n)
		{
			unordered_map < string, int > record;
			string auxiliary = "";
			for (int i = 0; i <= n - m; ++i)
			{
				auxiliary = text.substr(i, m);
				if (record.find(auxiliary) != record.end())
				{
					// Increase frequency
					record[auxiliary] = record[auxiliary] + 1;
				}
				else
				{
					// Add new key value 
					record[auxiliary] = 1;
				}
			}
			for (auto &v: record)
			{
				if (v.second == k)
				{
					result++;
				}
			}
		}
		if (result == 0)
		{
			cout << "\n None ";
		}
		else
		{
			cout << "\n  " << result;
		}
	}
};
int main()
{
	Substrings *task = new Substrings();
	string text = "itiopvitiiop";
	int m = 2;
	int k = 2;
	// Test A 
	// str = itiopvitiiop
	// m = 2 length of 2
	// k = 2 occurrence of 2
	// [op, ti,  io, it]
	// Output : 4
	task->findNlengthKoccurs(text, m, k);
	text = "xxxyyyzzztp";
	m = 3;
	k = 1;
	// Test B 
	// str = itiopvitiiop
	// m = 3 length of 3
	// k = 1 occurrence of 1
	// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	// Output : 9
	task->findNlengthKoccurs(text, m, k);
	return 0;
}

Output

  4
  9
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Count M-length substrings occurring exactly K times in a string
*/
public class Substrings
{
	public void findNlengthKoccurs(String text, int m, int k)
	{
		// Get the length of given text 
		int n = text.Length;
		int result = 0;
		if (k > 0 && k < n && m > 0 && m < n)
		{
			Dictionary < string, int > record = 
              new Dictionary < string, int > ();
			String auxiliary = "";
			for (int i = 0; i <= n - m; ++i)
			{
				auxiliary = text.Substring(i, m);
				if (record.ContainsKey(auxiliary))
				{
					// Increase frequency
					record[auxiliary] = record[auxiliary] + 1;
				}
				else
				{
					// Add new key value 
					record.Add(auxiliary, 1);
				}
			}
			foreach(KeyValuePair < String, int > v in record)
			{
				if (v.Value == k)
				{
					result++;
				}
			}
		}
		if (result == 0)
		{
			Console.Write("\n None ");
		}
		else
		{
			Console.Write("\n  " + result);
		}
	}
	public static void Main(String[] args)
	{
		Substrings task = new Substrings();
		String text = "itiopvitiiop";
		int m = 2;
		int k = 2;
		// Test A 
		// str = itiopvitiiop
		// m = 2 length of 2
		// k = 2 occurrence of 2
		// [op, ti,  io, it]
		// Output : 4
		task.findNlengthKoccurs(text, m, k);
		text = "xxxyyyzzztp";
		m = 3;
		k = 1;
		// Test B 
		// str = itiopvitiiop
		// m = 3 length of 3
		// k = 1 occurrence of 1
		// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
		// Output : 9
		task.findNlengthKoccurs(text, m, k);
	}
}

Output

  4
  9
package main

import "fmt"
/*
    Go program for
    Count M-length substrings occurring exactly K 
    times in a string
*/

func findNlengthKoccurs(text string, m int, k int) {
	// Get the length of given text 
	var n int = len(text)
	var result int = 0
	if k > 0 && k < n && m > 0 && m < n {
		var record = make(map[string] int)
		var auxiliary string = ""
		for i := 0 ; i <= n - m ; i++ {
			auxiliary = text[i: i + m]
			if _, found := record[auxiliary] ; found {
				// Increase frequency
				record[auxiliary] = record[auxiliary] + 1
			} else {
				// Add new key value 
				record[auxiliary] = 1
			}
		}
		for _, v := range record {
			if  v == k {
				result++
			}
		}
	}
	if result == 0 {
		fmt.Print("\n None ")
	} else {
		fmt.Print("\n  ", result)
	}
}
func main() {

	var text string = "itiopvitiiop"
	var m int = 2
	var k int = 2
	// Test A 
	// str = itiopvitiiop
	// m = 2 length of 2
	// k = 2 occurrence of 2
	// [op, ti,  io, it]
	// Output : 4
	findNlengthKoccurs(text, m, k)
	text = "xxxyyyzzztp"
	m = 3
	k = 1
	// Test B 
	// str = itiopvitiiop
	// m = 3 length of 3
	// k = 1 occurrence of 1
	// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	// Output : 9
	findNlengthKoccurs(text, m, k)
}

Output

  4
  9
<?php
/*
    Php program for
    Count M-length substrings occurring exactly K times in a string
*/
class Substrings
{
	public	function findNlengthKoccurs($text, $m, $k)
	{
		// Get the length of given text 
		$n = strlen($text);
		$result = 0;
		if ($k > 0 && $k < $n && $m > 0 && $m < $n)
		{
			$record = array();
			$auxiliary = "";
			for ($i = 0; $i <= $n - $m; ++$i)
			{
				$auxiliary = substr($text, $i, $m);
				if (array_key_exists($auxiliary, $record))
				{
					// Increase frequency
					$record[$auxiliary] = $record[$auxiliary] + 1;
				}
				else
				{
					// Add new key value 
					$record[$auxiliary] = 1;
				}
			}
			foreach($record as $key => $value)
			{
				if ($value == $k)
				{
					$result++;
				}
			}
		}
		if ($result == 0)
		{
			echo("\n None ");
		}
		else
		{
			echo("\n  ".$result);
		}
	}
}

function main()
{
	$task = new Substrings();
	$text = "itiopvitiiop";
	$m = 2;
	$k = 2;
	// Test A 
	// str = itiopvitiiop
	// m = 2 length of 2
	// k = 2 occurrence of 2
	// [op, ti,  io, it]
	// Output : 4
	$task->findNlengthKoccurs($text, $m, $k);
	$text = "xxxyyyzzztp";
	$m = 3;
	$k = 1;
	// Test B 
	// str = itiopvitiiop
	// m = 3 length of 3
	// k = 1 occurrence of 1
	// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	// Output : 9
	$task->findNlengthKoccurs($text, $m, $k);
}
main();

Output

  4
  9
/*
    Node JS program for
    Count M-length substrings occurring exactly K times in a string
*/
class Substrings
{
	findNlengthKoccurs(text, m, k)
	{
		// Get the length of given text 
		var n = text.length;
		var result = 0;
		if (k > 0 && k < n && m > 0 && m < n)
		{
			var record = new Map();
			var auxiliary = "";
			for (var i = 0; i <= n - m; ++i)
			{
				auxiliary = text.substring(i, i+m);
				if (record.has(auxiliary))
				{
					// Increase frequency
					record.set(auxiliary, record.get(auxiliary) + 1);
				}
				else
				{
					// Add new key value 
					record.set(auxiliary, 1);
				}
			}
			for (let [key, value] of record)
			{
				if (value == k)
				{
					result++;
				}
			}
		}
		if (result == 0)
		{
			process.stdout.write("\n None ");
		}
		else
		{
			process.stdout.write("\n  " + result);
		}
	}
}

function main()
{
	var task = new Substrings();
	var text = "itiopvitiiop";
	var m = 2;
	var k = 2;
	// Test A 
	// str = itiopvitiiop
	// m = 2 length of 2
	// k = 2 occurrence of 2
	// [op, ti,  io, it]
	// Output : 4
	task.findNlengthKoccurs(text, m, k);
	text = "xxxyyyzzztp";
	m = 3;
	k = 1;
	// Test B 
	// str = itiopvitiiop
	// m = 3 length of 3
	// k = 1 occurrence of 1
	// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	// Output : 9
	task.findNlengthKoccurs(text, m, k);
}
main();

Output

  4
  9
#    Python 3 program for
#    Count M-length substrings occurring exactly K times in a string
class Substrings :
	def findNlengthKoccurs(self, text, m, k) :
		#  Get the length of given text 
		n = len(text)
		result = 0
		if (k > 0 and k < n and m > 0 and m < n) :
			record = dict()
			auxiliary = ""
			i = 0
			while (i <= n - m) :
				auxiliary = text[i: i + m]
				if ((auxiliary in record.keys())) :
					#  Increase frequency
					record[auxiliary] = record.get(auxiliary) + 1
				else :
					#  Add new key value 
					record[auxiliary] = 1
				
				i += 1
			
			for key, value in record.items() :
				if (value == k) :
					result += 1
				
			
		
		if (result == 0) :
			print("\n None ", end = "")
		else :
			print("\n  ", result, end = "")
		
	

def main() :
	task = Substrings()
	text = "itiopvitiiop"
	m = 2
	k = 2
	#  Test A 
	#  str = itiopvitiiop
	#  m = 2 length of 2
	#  k = 2 occurrence of 2
	#  [op, ti,  io, it]
	#  Output : 4
	task.findNlengthKoccurs(text, m, k)
	text = "xxxyyyzzztp"
	m = 3
	k = 1
	#  Test B 
	#  str = itiopvitiiop
	#  m = 3 length of 3
	#  k = 1 occurrence of 1
	#  [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	#  Output : 9
	task.findNlengthKoccurs(text, m, k)

if __name__ == "__main__": main()

Output

   4
   9
#    Ruby program for
#    Count M-length substrings occurring exactly K times in a string
class Substrings 
	def findNlengthKoccurs(text, m, k) 
		#  Get the length of given text 
		n = text.length
		result = 0
		if (k > 0 && k < n && m > 0 && m < n) 
			record = Hash.new()
			auxiliary = ""
			i = 0
			while (i <= n - m) 
				auxiliary = text[i...i + m]
				if (record.key?(auxiliary)) 
					#  Increase frequency
					record[auxiliary] = record[auxiliary] + 1
				else
 
					#  Add new key value 
					record[auxiliary] = 1
				end

				i += 1
			end

			record.each { | key, value |
				if (value == k) 
					result += 1
				end

			}
		end

		if (result == 0) 
			print("\n None ")
		else
 
			print("\n  ", result)
		end

	end

end

def main() 
	task = Substrings.new()
	text = "itiopvitiiop"
	m = 2
	k = 2
	#  Test A 
	#  str = itiopvitiiop
	#  m = 2 length of 2
	#  k = 2 occurrence of 2
	#  [op, ti,  io, it]
	#  Output : 4
	task.findNlengthKoccurs(text, m, k)
	text = "xxxyyyzzztp"
	m = 3
	k = 1
	#  Test B 
	#  str = itiopvitiiop
	#  m = 3 length of 3
	#  k = 1 occurrence of 1
	#  [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	#  Output : 9
	task.findNlengthKoccurs(text, m, k)
end

main()

Output

  4
  9
import scala.collection.mutable._;
/*
    Scala program for
    Count M-length substrings occurring exactly K times in a string
*/
class Substrings()
{
	def findNlengthKoccurs(text: String, m: Int, k: Int): Unit = {
		// Get the length of given text 
		var n: Int = text.length();
		var result: Int = 0;
		if (k > 0 && k < n && m > 0 && m < n)
		{
			var record: HashMap[String, Int] = 
              new HashMap[String, Int]();
			var auxiliary: String = "";
			var i: Int = 0;
			while (i <= n - m)
			{
				auxiliary = text.substring(i, i + m);
				if (record.contains(auxiliary))
				{
					// Increase frequency
					record.addOne(auxiliary, 
                                  record.get(auxiliary).get + 1);
				}
				else
				{
					// Add new key value 
					record.addOne(auxiliary, 1);
				}
				i += 1;
			}
			for ((key, value) <- record)
			{
				if (value == k)
				{
					result += 1;
				}
			}
		}
		if (result == 0)
		{
			print("\n None ");
		}
		else
		{
			print("\n  " + result);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Substrings = new Substrings();
		var text: String = "itiopvitiiop";
		var m: Int = 2;
		var k: Int = 2;
		// Test A 
		// str = itiopvitiiop
		// m = 2 length of 2
		// k = 2 occurrence of 2
		// [op, ti,  io, it]
		// Output : 4
		task.findNlengthKoccurs(text, m, k);
		text = "xxxyyyzzztp";
		m = 3;
		k = 1;
		// Test B 
		// str = itiopvitiiop
		// m = 3 length of 3
		// k = 1 occurrence of 1
		// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
		// Output : 9
		task.findNlengthKoccurs(text, m, k);
	}
}

Output

  4
  9
import Foundation;
/*
    Swift 4 program for
    Count M-length substrings occurring exactly K times in a string
*/
class Substrings
{
	func findNlengthKoccurs(_ text: String, _ m: Int, _ k: Int)
	{
		// Get the length of given text 
		let n: Int = text.count;
		var result: Int = 0;
		if (k > 0 && k < n && m > 0 && m < n)
		{
			var record  = [String : Int]();
			var auxiliary: String = "";
			var i: Int = 0;
          	var t = Array(text);
			while (i <= n - m)
			{
                let range = i..<(i+m)
				auxiliary = String(t[range]);
				if (record.keys.contains(auxiliary))
				{
					// Increase frequency
					record[auxiliary] = record[auxiliary]! + 1;
				}
				else
				{
					// Add new key value 
					record[auxiliary] = 1;
				}
				i += 1;
			}
			for (_, value) in record
			{
				if (value == k)
				{
					result += 1;
				}
			}
		}
		if (result == 0)
		{
			print("\n None ", terminator: "");
		}
		else
		{
			print("\n  ", result, terminator: "");
		}
	}
}
func main()
{
	let task: Substrings = Substrings();
	var text: String = "itiopvitiiop";
	var m: Int = 2;
	var k: Int = 2;
	// Test A 
	// str = itiopvitiiop
	// m = 2 length of 2
	// k = 2 occurrence of 2
	// [op, ti,  io, it]
	// Output : 4
	task.findNlengthKoccurs(text, m, k);
	text = "xxxyyyzzztp";
	m = 3;
	k = 1;
	// Test B 
	// str = itiopvitiiop
	// m = 3 length of 3
	// k = 1 occurrence of 1
	// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	// Output : 9
	task.findNlengthKoccurs(text, m, k);
}
main();

Output

   4
   9
/*
    Kotlin program for
    Count M-length substrings occurring exactly K times in a string
*/
class Substrings
{
	fun findNlengthKoccurs(text: String, m: Int, k: Int): Unit
	{
		// Get the length of given text 
		val n: Int = text.length;
		var result: Int = 0;
		if (k > 0 && k < n && m > 0 && m < n)
		{
			val record: HashMap < String, Int > = 
              HashMap < String, Int > ();
			var auxiliary: String ;
			var i: Int = 0;
			while (i <= n - m)
			{
				auxiliary = text.substring(i, i + m);
				if (record.containsKey(auxiliary))
				{
					// Increase frequency
					record.put(auxiliary, record.getValue(auxiliary) + 1);
				}
				else
				{
					// Add new key value 
					record.put(auxiliary, 1);
				}
				i += 1;
			}
			for ((_, value) in record)
			{
				if (value == k)
				{
					result += 1;
				}
			}
		}
		if (result == 0)
		{
			print("\n None ");
		}
		else
		{
			print("\n  " + result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Substrings = Substrings();
	var text: String = "itiopvitiiop";
	var m: Int = 2;
	var k: Int = 2;
	// Test A 
	// str = itiopvitiiop
	// m = 2 length of 2
	// k = 2 occurrence of 2
	// [op, ti,  io, it]
	// Output : 4
	task.findNlengthKoccurs(text, m, k);
	text = "xxxyyyzzztp";
	m = 3;
	k = 1;
	// Test B 
	// str = itiopvitiiop
	// m = 3 length of 3
	// k = 1 occurrence of 1
	// [zzt, ztp, xxy, yyy, yzz, xxx, xyy, yyz, zzz]
	// Output : 9
	task.findNlengthKoccurs(text, m, k);
}

Output

  4
  9
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