Skip to main content

Longest subsequence where each character appears at least k times

Here given code implementation process.

import java.util.HashMap;
/*
    Java program for
    Longest subsequence where each character appears at least k times
*/
public class Subsequence
{
	public void kCharacterSubsequence(String text, int k)
	{
		// Get the length of given text 
		int n = text.length();
		if (n == 0 || k < 0)
		{
			return;
		}
		HashMap < Character, Integer > record = 
          new HashMap < Character, Integer > ();
		String result = "";
		for (int i = 0; i < n; ++i)
		{
			if (record.containsKey(text.charAt(i)))
			{
				// Increase frequency
				record.put(text.charAt(i), 
                           record.get(text.charAt(i)) + 1);
			}
			else
			{
				// Add new key value 
				record.put(text.charAt(i), 1);
			}
		}
      	// Add element which is occurring at least K times
		for (int i = 0; i < n; ++i)
		{
			if (record.get(text.charAt(i)) >= k)
			{   
				result = result + text.charAt(i);
			}
		}
		if (result.length() == 0)
		{
			System.out.print("None");
		}
		else
		{
			System.out.println(result);
		}
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text = "abcpcdxyabzdaced";
		int k = 2;
		// Example A
		// str = abccdabdaced
		// k = 2 occurrence at least 2 times
		// [
		//      p : 1
		//      a : 3    3 >= k
		//      b : 2    2 >= k
		//      c : 3    3 >= k
		//      d : 3    3 >= k
		//      e : 1
		//      x : 1
		//      y : 1
		//      z : 1
		// ]
		// Output : abccdabdacd
		task.kCharacterSubsequence(text, k);
		k = 3;
		// Example B
		// str = abccdabdaced
		// k = 3 occurrence at least 3 times
		// [
		//      p : 1
		//      a : 3    3 >= k
		//      b : 2 
		//      c : 3    3 >= k
		//      d : 3    3 >= k
		//      e : 1
		//      x : 1
		//      y : 1
		//      z : 1
		// ]
		// Output : accdadacd
		task.kCharacterSubsequence(text, k);
	}
}

Output

abccdabdacd
accdadacd
// Include header file
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;
/*
    C++ program for
    Longest subsequence where each character 
    appears at least k times
*/
class Subsequence
{
	public: void kCharacterSubsequence(string text, int k)
	{
		// Get the length of given text 
		int n = text.length();
		if (n == 0 || k < 0)
		{
			return;
		}
		unordered_map < char, int > record;
		string result = "";
		for (int i = 0; i < n; ++i)
		{
			if (record.find(text[i]) != record.end())
			{
				// Increase frequency
				record[text[i]] = record[text[i]] + 1;
			}
			else
			{
				// Add new key value 
				record[text[i]] = 1;
			}
		}
		// Add element which is occurring at least K times
		for (int i = 0; i < n; ++i)
		{
			if (record[text[i]] >= k)
			{
				result = result  +  text[i];
			}
		}
		if (result.length() == 0)
		{
			cout << "None";
		}
		else
		{
			cout << result << endl;
		}
	}
};
int main()
{
	Subsequence *task = new Subsequence();
	string text = "abcpcdxyabzdaced";
	int k = 2;
	// Example A
	// str = abccdabdaced
	// k = 2 occurrence at least 2 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2    2 >= k
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : abccdabdacd
	task->kCharacterSubsequence(text, k);
	k = 3;
	// Example B
	// str = abccdabdaced
	// k = 3 occurrence at least 3 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2 
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : accdadacd
	task->kCharacterSubsequence(text, k);
	return 0;
}

Output

abccdabdacd
accdadacd
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Longest subsequence where each character appears at least k times
*/
public class Subsequence
{
	public void kCharacterSubsequence(String text, int k)
	{
		// Get the length of given text 
		int n = text.Length;
		if (n == 0 || k < 0)
		{
			return;
		}
		Dictionary < char, int > record = 
          new Dictionary < char, int > ();
		String result = "";
		for (int i = 0; i < n; ++i)
		{
			if (record.ContainsKey(text[i]))
			{
				// Increase frequency
				record[text[i]] = record[text[i]] + 1;
			}
			else
			{
				// Add new key value 
				record.Add(text[i], 1);
			}
		}
		// Add element which is occurring at least K times
		for (int i = 0; i < n; ++i)
		{
			if (record[text[i]] >= k)
			{
				result = result + text[i];
			}
		}
		if (result.Length == 0)
		{
			Console.Write("None");
		}
		else
		{
			Console.WriteLine(result);
		}
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text = "abcpcdxyabzdaced";
		int k = 2;
		// Example A
		// str = abccdabdaced
		// k = 2 occurrence at least 2 times
		// [
		//      p : 1
		//      a : 3    3 >= k
		//      b : 2    2 >= k
		//      c : 3    3 >= k
		//      d : 3    3 >= k
		//      e : 1
		//      x : 1
		//      y : 1
		//      z : 1
		// ]
		// Output : abccdabdacd
		task.kCharacterSubsequence(text, k);
		k = 3;
		// Example B
		// str = abccdabdaced
		// k = 3 occurrence at least 3 times
		// [
		//      p : 1
		//      a : 3    3 >= k
		//      b : 2 
		//      c : 3    3 >= k
		//      d : 3    3 >= k
		//      e : 1
		//      x : 1
		//      y : 1
		//      z : 1
		// ]
		// Output : accdadacd
		task.kCharacterSubsequence(text, k);
	}
}

Output

abccdabdacd
accdadacd
package main
import "fmt"
/*
    Go program for
    Longest subsequence where each character appears at 
    least k times
*/

func kCharacterSubsequence(text string, k int) {
	// Get the length of given text 
	var n int = len(text)
	if n == 0 || k < 0 {
		return
	}
	var record = make(map[byte] int)
	var result string = ""
	for i := 0 ; i < n ; i++ {
		if _, found := record[text[i]] ; found {
			// Increase frequency
			record[text[i]] = record[text[i]] + 1
		} else {
			// Add new key value 
			record[text[i]] = 1
		}
	}
	// Add element which is occurring at least K times
	for i := 0 ; i < n ; i++ {
		if record[text[i]] >= k {
			result = result + string(text[i])
		}
	}
	if len(result) == 0 {
		fmt.Print("None")
	} else {
		fmt.Println(result)
	}
}
func main() {

	var text string = "abcpcdxyabzdaced"
	var k int = 2
	// Example A
	// str = abccdabdaced
	// k = 2 occurrence at least 2 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2    2 >= k
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : abccdabdacd
	kCharacterSubsequence(text, k)
	k = 3
	// Example B
	// str = abccdabdaced
	// k = 3 occurrence at least 3 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2 
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : accdadacd
	kCharacterSubsequence(text, k)
}

Output

abccdabdacd
accdadacd
<?php
/*
    Php program for
    Longest subsequence where each character appears at least k times
*/
class Subsequence
{
	public	function kCharacterSubsequence($text, $k)
	{
		// Get the length of given text 
		$n = strlen($text);
		if ($n == 0 || $k < 0)
		{
			return;
		}
		$record = array();
		$result = "";
		for ($i = 0; $i < $n; ++$i)
		{
			if (array_key_exists($text[$i], $record))
			{
				// Increase frequency
				$record[$text[$i]] = $record[$text[$i]] + 1;
			}
			else
			{
				// Add new key value 
				$record[$text[$i]] = 1;
			}
		}
		// Add element which is occurring at least K times
		for ($i = 0; $i < $n; ++$i)
		{
			if ($record[$text[$i]] >= $k)
			{
				$result = $result.strval($text[$i]);
			}
		}
		if (strlen($result) == 0)
		{
			echo("None");
		}
		else
		{
			echo($result.
				"\n");
		}
	}
}

function main()
{
	$task = new Subsequence();
	$text = "abcpcdxyabzdaced";
	$k = 2;
	// Example A
	// str = abccdabdaced
	// k = 2 occurrence at least 2 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2    2 >= k
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : abccdabdacd
	$task->kCharacterSubsequence($text, $k);
	$k = 3;
	// Example B
	// str = abccdabdaced
	// k = 3 occurrence at least 3 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2 
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : accdadacd
	$task->kCharacterSubsequence($text, $k);
}
main();

Output

abccdabdacd
accdadacd
/*
    Node JS program for
    Longest subsequence where each character appears at least k times
*/
class Subsequence
{
	kCharacterSubsequence(text, k)
	{
		// Get the length of given text 
		var n = text.length;
		if (n == 0 || k < 0)
		{
			return;
		}
		var record = new Map();
		var result = "";
		for (var i = 0; i < n; ++i)
		{
			if (record.has(text.charAt(i)))
			{
				// Increase frequency
				record.set(text.charAt(i), 
                           record.get(text.charAt(i)) + 1);
			}
			else
			{
				// Add new key value 
				record.set(text.charAt(i), 1);
			}
		}
		// Add element which is occurring at least K times
		for (var i = 0; i < n; ++i)
		{
			if (record.get(text.charAt(i)) >= k)
			{
				result = result + text.charAt(i);
			}
		}
		if (result.length == 0)
		{
			process.stdout.write("None");
		}
		else
		{
			console.log(result);
		}
	}
}

function main()
{
	var task = new Subsequence();
	var text = "abcpcdxyabzdaced";
	var k = 2;
	// Example A
	// str = abccdabdaced
	// k = 2 occurrence at least 2 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2    2 >= k
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : abccdabdacd
	task.kCharacterSubsequence(text, k);
	k = 3;
	// Example B
	// str = abccdabdaced
	// k = 3 occurrence at least 3 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2 
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : accdadacd
	task.kCharacterSubsequence(text, k);
}
main();

Output

abccdabdacd
accdadacd
#    Python 3 program for
#    Longest subsequence where each character appears at least k times
class Subsequence :
	def kCharacterSubsequence(self, text, k) :
		#  Get the length of given text 
		n = len(text)
		if (n == 0 or k < 0) :
			return
		
		record = dict()
		result = ""
		i = 0
		while (i < n) :
			if ((text[i] in record.keys())) :
				#  Increase frequency
				record[text[i]] = record.get(text[i]) + 1
			else :
				#  Add new key value 
				record[text[i]] = 1
			
			i += 1
		
		i = 0
		#  Add element which is occurring at least K times
		while (i < n) :
			if (record.get(text[i]) >= k) :
				result = result + str(text[i])
			
			i += 1
		
		if (len(result) == 0) :
			print("None", end = "")
		else :
			print(result)
		
	

def main() :
	task = Subsequence()
	text = "abcpcdxyabzdaced"
	k = 2
	#  Example A
	#  str = abccdabdaced
	#  k = 2 occurrence at least 2 times
	#  [
	#       p : 1
	#       a : 3    3 >= k
	#       b : 2    2 >= k
	#       c : 3    3 >= k
	#       d : 3    3 >= k
	#       e : 1
	#       x : 1
	#       y : 1
	#       z : 1
	#  ]
	#  Output : abccdabdacd
	task.kCharacterSubsequence(text, k)
	k = 3
	#  Example B
	#  str = abccdabdaced
	#  k = 3 occurrence at least 3 times
	#  [
	#       p : 1
	#       a : 3    3 >= k
	#       b : 2 
	#       c : 3    3 >= k
	#       d : 3    3 >= k
	#       e : 1
	#       x : 1
	#       y : 1
	#       z : 1
	#  ]
	#  Output : accdadacd
	task.kCharacterSubsequence(text, k)

if __name__ == "__main__": main()

Output

abccdabdacd
accdadacd
#    Ruby program for
#    Longest subsequence where each character appears at least k times
class Subsequence 
	def kCharacterSubsequence(text, k) 
		#  Get the length of given text 
		n = text.length
		if (n == 0 || k < 0) 
			return
		end

		record = Hash.new()
		result = ""
		i = 0
		while (i < n) 
			if (record.key?(text[i])) 
				#  Increase frequency
				record[text[i]] = record[text[i]] + 1
			else
 
				#  Add new key value 
				record[text[i]] = 1
			end

			i += 1
		end

		i = 0
		#  Add element which is occurring at least K times
		while (i < n) 
			if (record[text[i]] >= k) 
				result = result + text[i].to_s
			end

			i += 1
		end

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

	end

end

def main() 
	task = Subsequence.new()
	text = "abcpcdxyabzdaced"
	k = 2
	#  Example A
	#  str = abccdabdaced
	#  k = 2 occurrence at least 2 times
	#  [
	#       p : 1
	#       a : 3    3 >= k
	#       b : 2    2 >= k
	#       c : 3    3 >= k
	#       d : 3    3 >= k
	#       e : 1
	#       x : 1
	#       y : 1
	#       z : 1
	#  ]
	#  Output : abccdabdacd
	task.kCharacterSubsequence(text, k)
	k = 3
	#  Example B
	#  str = abccdabdaced
	#  k = 3 occurrence at least 3 times
	#  [
	#       p : 1
	#       a : 3    3 >= k
	#       b : 2 
	#       c : 3    3 >= k
	#       d : 3    3 >= k
	#       e : 1
	#       x : 1
	#       y : 1
	#       z : 1
	#  ]
	#  Output : accdadacd
	task.kCharacterSubsequence(text, k)
end

main()

Output

abccdabdacd
accdadacd

import scala.collection.mutable._;
/*
    Scala program for
    Longest subsequence where each character appears at least k times
*/
class Subsequence()
{
	def kCharacterSubsequence(text: String, k: Int): Unit = {
		// Get the length of given text 
		var n: Int = text.length();
		if (n == 0 || k < 0)
		{
			return;
		}
		var record = new HashMap[Character, Int]();
		var result: String = "";
		var i: Int = 0;
		while (i < n)
		{
			if (record.contains(text.charAt(i)))
			{
				// Increase frequency
				record.addOne(text.charAt(i), 
                              record.get(text.charAt(i)).get + 1);
			}
			else
			{
				// Add new key value 
				record.addOne(text.charAt(i), 1);
			}
			i += 1;
		}
		i = 0;
		// Add element which is occurring at least K times
		while (i < n)
		{
			if (record.get(text.charAt(i)).get >= k)
			{
				result = result + text.charAt(i).toString();
			}
			i += 1;
		}
		if (result.length() == 0)
		{
			print("None");
		}
		else
		{
			println(result);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		var text: String = "abcpcdxyabzdaced";
		var k: Int = 2;
		// Example A
		// str = abccdabdaced
		// k = 2 occurrence at least 2 times
		// [
		//      p : 1
		//      a : 3    3 >= k
		//      b : 2    2 >= k
		//      c : 3    3 >= k
		//      d : 3    3 >= k
		//      e : 1
		//      x : 1
		//      y : 1
		//      z : 1
		// ]
		// Output : abccdabdacd
		task.kCharacterSubsequence(text, k);
		k = 3;
		// Example B
		// str = abccdabdaced
		// k = 3 occurrence at least 3 times
		// [
		//      p : 1
		//      a : 3    3 >= k
		//      b : 2 
		//      c : 3    3 >= k
		//      d : 3    3 >= k
		//      e : 1
		//      x : 1
		//      y : 1
		//      z : 1
		// ]
		// Output : accdadacd
		task.kCharacterSubsequence(text, k);
	}
}

Output

abccdabdacd
accdadacd
import Foundation;
/*
    Swift 4 program for
    Longest subsequence where each character appears at least k times
*/
class Subsequence
{
	func kCharacterSubsequence(_ data: String, _ k: Int)
	{
		// Get the length of given text 
		let n: Int = data.count;
		if (n == 0 || k < 0)
		{
			return;
		}
      	let text = Array(data);
		var record = [Character : Int]();
		var result: String = "";
		var i: Int = 0;
		while (i < n)
		{
			if (record.keys.contains(text[i]))
			{
				// Increase frequency
				record[text[i]] = record[text[i]]! + 1;
			}
			else
			{
				// Add new key value 
				record[text[i]] = 1;
			}
			i += 1;
		}
		i = 0;
		// Add element which is occurring at least K times
		while (i < n)
		{
			if (record[text[i]]! >= k)
			{
				result = result + String(text[i]);
			}
			i += 1;
		}
		if (result.count == 0)
		{
			print("None", terminator: "");
		}
		else
		{
			print(result);
		}
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	let text: String = "abcpcdxyabzdaced";
	var k: Int = 2;
	// Example A
	// str = abccdabdaced
	// k = 2 occurrence at least 2 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2    2 >= k
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : abccdabdacd
	task.kCharacterSubsequence(text, k);
	k = 3;
	// Example B
	// str = abccdabdaced
	// k = 3 occurrence at least 3 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2 
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : accdadacd
	task.kCharacterSubsequence(text, k);
}
main();

Output

abccdabdacd
accdadacd
/*
    Kotlin program for
    Longest subsequence where each character appears at least k times
*/
class Subsequence
{
	fun kCharacterSubsequence(text: String, k: Int): Unit
	{
		// Get the length of given text 
		val n: Int = text.length;
		if (n == 0 || k < 0)
		{
			return;
		}
		var record = HashMap < Char, Int > ();
		var result: String = "";
		var i: Int = 0;
		while (i < n)
		{
			if (record.containsKey(text.get(i)))
			{
				// Increase frequency
				record.put(text.get(i), 
                           record.getValue(text.get(i)) + 1);
			}
			else
			{
				// Add new key value 
				record.put(text.get(i), 1);
			}
			i += 1;
		}
		i = 0;
		// Add element which is occurring at least K times
		while (i < n)
		{
			if (record.getValue(text.get(i)) >= k)
			{
				result = result + text.get(i).toString();
			}
			i += 1;
		}
		if (result.length == 0)
		{
			print("None");
		}
		else
		{
			println(result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	val text: String = "abcpcdxyabzdaced";
	var k: Int = 2;
	// Example A
	// str = abccdabdaced
	// k = 2 occurrence at least 2 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2    2 >= k
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : abccdabdacd
	task.kCharacterSubsequence(text, k);
	k = 3;
	// Example B
	// str = abccdabdaced
	// k = 3 occurrence at least 3 times
	// [
	//      p : 1
	//      a : 3    3 >= k
	//      b : 2 
	//      c : 3    3 >= k
	//      d : 3    3 >= k
	//      e : 1
	//      x : 1
	//      y : 1
	//      z : 1
	// ]
	// Output : accdadacd
	task.kCharacterSubsequence(text, k);
}

Output

abccdabdacd
accdadacd
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