Skip to main content

Find the frequency of subsequence in given string

Here given code implementation process.

/*
    Java program for
    Find the frequency of subsequence in given string
*/
public class Subsequence
{
	public void countSubSequence(String text, String sequence)
	{
		// Get the length of given parameters
		int n = text.length();
		int m = sequence.length();
		int[][] dp = new int[n + 1][m + 1];
		// Set initial value of first column
		for (int i = 1; i <= n; ++i)
		{
			dp[i][0] = 1;
		}
		// Set initial value of first row
		for (int i = 1; i <= m; ++i)
		{
			dp[0][i] = 0;
		}
		// Active first row first column
		dp[0][0] = 1;
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= m; ++j)
			{
				if (text.charAt(i - 1) == sequence.charAt(j - 1))
				{
					// Change element value by using sum of top two elements
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				}
				else
				{
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		// Display calculated result
		System.out.println(dp[n][m]);
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text = "aaabbb";
		String sequence = "ab";
		/*
		    text = aaabbb
		    -------------
		    subsequence = ab
		    
		        a a a b b b
		    ➀   -     -    ->ab
		        a a a b b b
		    ➁   -       -   ->ab
		        a a a b b b
		    ➂   -         - ->ab
		        a a a b b b
		    ➃     -   -     ->ab
		        a a a b b b
		    ➄     -     -   ->ab
		        a a a b b b
		    ➅     -       - ->ab
		        a a a b b b
		    ➆       - -     ->ab
		        a a a b b b
		    ➇       -   -   ->ab 
		        a a a b b b            
		    ➈       -     - ->ab 
		    ______________________
		    Result = 9
		*/
		task.countSubSequence(text, sequence);
	}
}

Output

9
// Include header file
#include <iostream>

#include <string>

using namespace std;
/*
    C++ program for
    Find the frequency of subsequence in given string
*/
class Subsequence
{
	public: void countSubSequence(string text, string sequence)
	{
		// Get the length of given parameters
		int n = text.length();
		int m = sequence.length();
		int dp[n + 1][m + 1];
		// Set initial value of first column
		for (int i = 1; i <= n; ++i)
		{
			dp[i][0] = 1;
		}
		// Set initial value of first row
		for (int i = 1; i <= m; ++i)
		{
			dp[0][i] = 0;
		}
		// Active first row first column
		dp[0][0] = 1;
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= m; ++j)
			{
				if (text[i - 1] == sequence[j - 1])
				{
					// Change element value by using sum of top two elements
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				}
				else
				{
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		// Display calculated result
		cout << dp[n][m] << endl;
	}
};
int main()
{
	Subsequence *task = new Subsequence();
	string text = "aaabbb";
	string sequence = "ab";
	/*
	    text = aaabbb
	    -------------
	    subsequence = ab
	    
	        a a a b b b
	    ➀   -     -    ->ab
	        a a a b b b
	    ➁   -       -   ->ab
	        a a a b b b
	    ➂   -         - ->ab
	        a a a b b b
	    ➃     -   -     ->ab
	        a a a b b b
	    ➄     -     -   ->ab
	        a a a b b b
	    ➅     -       - ->ab
	        a a a b b b
	    ➆       - -     ->ab
	        a a a b b b
	    ➇       -   -   ->ab 
	        a a a b b b            
	    ➈       -     - ->ab 
	    ______________________
	    Result = 9
	*/
	task->countSubSequence(text, sequence);
	return 0;
}

Output

9
// Include namespace system
using System;
/*
    Csharp program for
    Find the frequency of subsequence in given string
*/
public class Subsequence
{
	public void countSubSequence(String text, String sequence)
	{
		// Get the length of given parameters
		int n = text.Length;
		int m = sequence.Length;
		int[,] dp = new int[n + 1,m + 1];
		// Set initial value of first column
		for (int i = 1; i <= n; ++i)
		{
			dp[i,0] = 1;
		}
		// Set initial value of first row
		for (int i = 1; i <= m; ++i)
		{
			dp[0,i] = 0;
		}
		// Active first row first column
		dp[0,0] = 1;
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= m; ++j)
			{
				if (text[i - 1] == sequence[j - 1])
				{
					// Change element value by using sum of top two elements
					dp[i,j] = dp[i - 1,j - 1] + dp[i - 1,j];
				}
				else
				{
					dp[i,j] = dp[i - 1,j];
				}
			}
		}
		// Display calculated result
		Console.WriteLine(dp[n,m]);
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text = "aaabbb";
		String sequence = "ab";
		/*
		    text = aaabbb
		    -------------
		    subsequence = ab
		    
		        a a a b b b
		    ➀   -     -    ->ab
		        a a a b b b
		    ➁   -       -   ->ab
		        a a a b b b
		    ➂   -         - ->ab
		        a a a b b b
		    ➃     -   -     ->ab
		        a a a b b b
		    ➄     -     -   ->ab
		        a a a b b b
		    ➅     -       - ->ab
		        a a a b b b
		    ➆       - -     ->ab
		        a a a b b b
		    ➇       -   -   ->ab 
		        a a a b b b            
		    ➈       -     - ->ab 
		    ______________________
		    Result = 9
		*/
		task.countSubSequence(text, sequence);
	}
}

Output

9
package main
import "fmt"
/*
    Go program for
    Find the frequency of subsequence in given string
*/

func countSubSequence(text, sequence string) {
	// Get the length of given parameters
	var n int = len(text)
	var m int = len(sequence)
	var dp = make([][] int, n + 1)
	for i:= 0; i <= n ; i++{
		dp[i] = make([]int, m + 1)
	}
	// Set initial value of first column
	for i := 1 ; i <= n ; i++ {
		dp[i][0] = 1
	}
	// Set initial value of first row
	for i := 1 ; i <= m ; i++ {
		dp[0][i] = 0
	}
	// Active first row first column
	dp[0][0] = 1
	for i := 1 ; i <= n ; i++ {
		for j := 1 ; j <= m ; j++ {
			if text[i - 1] == sequence[j - 1] {
				// Change element value by using sum of top two elements
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
			} else {
				dp[i][j] = dp[i - 1][j]
			}
		}
	}
	// Display calculated result
	fmt.Println(dp[n][m])
}
func main() {

	var text string = "aaabbb"
	var sequence string = "ab"
	/*
	    text = aaabbb
	    -------------
	    subsequence = ab
	    
	        a a a b b b
	    ➀   -     -    ->ab
	        a a a b b b
	    ➁   -       -   ->ab
	        a a a b b b
	    ➂   -         - ->ab
	        a a a b b b
	    ➃     -   -     ->ab
	        a a a b b b
	    ➄     -     -   ->ab
	        a a a b b b
	    ➅     -       - ->ab
	        a a a b b b
	    ➆       - -     ->ab
	        a a a b b b
	    ➇       -   -   ->ab 
	        a a a b b b            
	    ➈       -     - ->ab 
	    ______________________
	    Result = 9
	*/
	countSubSequence(text, sequence)
}

Output

9
<?php
/*
    Php program for
    Find the frequency of subsequence in given string
*/
class Subsequence
{
	public	function countSubSequence($text, $sequence)
	{
		// Get the length of given parameters
		$n = strlen($text);
		$m = strlen($sequence);
		$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
		// Set initial value of first column
		for ($i = 1; $i <= $n; ++$i)
		{
			$dp[$i][0] = 1;
		}
		// Set initial value of first row
		for ($i = 1; $i <= $m; ++$i)
		{
			$dp[0][$i] = 0;
		}
		// Active first row first column
		$dp[0][0] = 1;
		for ($i = 1; $i <= $n; ++$i)
		{
			for ($j = 1; $j <= $m; ++$j)
			{
				if ($text[$i - 1] == $sequence[$j - 1])
				{
					// Change element value by using sum of top two elements
					$dp[$i][$j] = $dp[$i - 1][$j - 1] + $dp[$i - 1][$j];
				}
				else
				{
					$dp[$i][$j] = $dp[$i - 1][$j];
				}
			}
		}
		// Display calculated result
		echo($dp[$n][$m]."\n");
	}
}

function main()
{
	$task = new Subsequence();
	$text = "aaabbb";
	$sequence = "ab";
	/*
	    text = aaabbb
	    -------------
	    subsequence = ab
	    
	        a a a b b b
	    ➀   -     -    ->ab
	        a a a b b b
	    ➁   -       -   ->ab
	        a a a b b b
	    ➂   -         - ->ab
	        a a a b b b
	    ➃     -   -     ->ab
	        a a a b b b
	    ➄     -     -   ->ab
	        a a a b b b
	    ➅     -       - ->ab
	        a a a b b b
	    ➆       - -     ->ab
	        a a a b b b
	    ➇       -   -   ->ab 
	        a a a b b b            
	    ➈       -     - ->ab 
	    ______________________
	    Result = 9
	*/
	$task->countSubSequence($text, $sequence);
}
main();

Output

9
/*
    Node JS program for
    Find the frequency of subsequence in given string
*/
class Subsequence
{
	countSubSequence(text, sequence)
	{
		// Get the length of given parameters
		var n = text.length;
		var m = sequence.length;
		var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
		// Set initial value of first column
		for (var i = 1; i <= n; ++i)
		{
			dp[i][0] = 1;
		}
		// Set initial value of first row
		for (var i = 1; i <= m; ++i)
		{
			dp[0][i] = 0;
		}
		// Active first row first column
		dp[0][0] = 1;
		for (var i = 1; i <= n; ++i)
		{
			for (var j = 1; j <= m; ++j)
			{
				if (text.charAt(i - 1) == sequence.charAt(j - 1))
				{
					// Change element value by using sum of top two elements
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				}
				else
				{
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		// Display calculated result
		console.log(dp[n][m]);
	}
}

function main()
{
	var task = new Subsequence();
	var text = "aaabbb";
	var sequence = "ab";
	/*
	    text = aaabbb
	    -------------
	    subsequence = ab
	    
	        a a a b b b
	    ➀   -     -    ->ab
	        a a a b b b
	    ➁   -       -   ->ab
	        a a a b b b
	    ➂   -         - ->ab
	        a a a b b b
	    ➃     -   -     ->ab
	        a a a b b b
	    ➄     -     -   ->ab
	        a a a b b b
	    ➅     -       - ->ab
	        a a a b b b
	    ➆       - -     ->ab
	        a a a b b b
	    ➇       -   -   ->ab 
	        a a a b b b            
	    ➈       -     - ->ab 
	    ______________________
	    Result = 9
	*/
	task.countSubSequence(text, sequence);
}
main();

Output

9
#    Python 3 program for
#    Find the frequency of subsequence in given string
class Subsequence :
	def countSubSequence(self, text, sequence) :
		#  Get the length of given parameters
		n = len(text)
		m = len(sequence)
		dp = [[0] * (m + 1) for _ in range(n + 1) ]
		i = 1
		#  Set initial value of first column
		while (i <= n) :
			dp[i][0] = 1
			i += 1
		
		i = 1
		#  Set initial value of first row
		while (i <= m) :
			dp[0][i] = 0
			i += 1
		
		#  Active first row first column
		dp[0][0] = 1
		i = 1
		while (i <= n) :
			j = 1
			while (j <= m) :
				if (text[i - 1] == sequence[j - 1]) :
					#  Change element value by using sum of top two elements
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				else :
					dp[i][j] = dp[i - 1][j]
				
				j += 1
			
			i += 1
		
		#  Display calculated result
		print(dp[n][m])
	

def main() :
	task = Subsequence()
	text = "aaabbb"
	sequence = "ab"
	#    text = aaabbb
	#    -------------
	#    subsequence = ab
	#        a a a b b b
	#    ➀   -     -    ->ab
	#        a a a b b b
	#    ➁   -       -   ->ab
	#        a a a b b b
	#    ➂   -         - ->ab
	#        a a a b b b
	#    ➃     -   -     ->ab
	#        a a a b b b
	#    ➄     -     -   ->ab
	#        a a a b b b
	#    ➅     -       - ->ab
	#        a a a b b b
	#    ➆       - -     ->ab
	#        a a a b b b
	#    ➇       -   -   ->ab 
	#        a a a b b b            
	#    ➈       -     - ->ab 
	#    ______________________
	#    Result = 9
	task.countSubSequence(text, sequence)

if __name__ == "__main__": main()

Output

9
#    Ruby program for
#    Find the frequency of subsequence in given string
class Subsequence 
	def countSubSequence(text, sequence) 
		#  Get the length of given parameters
		n = text.length
		m = sequence.length
		dp = Array.new(n + 1) {Array.new(m + 1) {0}}
		i = 1
		#  Set initial value of first column
		while (i <= n) 
			dp[i][0] = 1
			i += 1
		end

		i = 1
		#  Set initial value of first row
		while (i <= m) 
			dp[0][i] = 0
			i += 1
		end

		#  Active first row first column
		dp[0][0] = 1
		i = 1
		while (i <= n) 
			j = 1
			while (j <= m) 
				if (text[i - 1] == sequence[j - 1]) 
					#  Change element value by using sum of top two elements
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				else
 
					dp[i][j] = dp[i - 1][j]
				end

				j += 1
			end

			i += 1
		end

		#  Display calculated result
		print(dp[n][m], "\n")
	end

end

def main() 
	task = Subsequence.new()
	text = "aaabbb"
	sequence = "ab"
	#    text = aaabbb
	#    -------------
	#    subsequence = ab
	#        a a a b b b
	#    ➀   -     -    ->ab
	#        a a a b b b
	#    ➁   -       -   ->ab
	#        a a a b b b
	#    ➂   -         - ->ab
	#        a a a b b b
	#    ➃     -   -     ->ab
	#        a a a b b b
	#    ➄     -     -   ->ab
	#        a a a b b b
	#    ➅     -       - ->ab
	#        a a a b b b
	#    ➆       - -     ->ab
	#        a a a b b b
	#    ➇       -   -   ->ab 
	#        a a a b b b            
	#    ➈       -     - ->ab 
	#    ______________________
	#    Result = 9
	task.countSubSequence(text, sequence)
end

main()

Output

9

import scala.collection.mutable._;
/*
    Scala program for
    Find the frequency of subsequence in given string
*/
class Subsequence()
{
	def countSubSequence(text: String, sequence: String): Unit = {
		// Get the length of given parameters
		var n: Int = text.length();
		var m: Int = sequence.length();
		var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
		var i: Int = 1;
		// Set initial value of first column
		while (i <= n)
		{
			dp(i)(0) = 1;
			i += 1;
		}
		i = 1;
		// Set initial value of first row
		while (i <= m)
		{
			dp(0)(i) = 0;
			i += 1;
		}
		// Active first row first column
		dp(0)(0) = 1;
		i = 1;
		while (i <= n)
		{
			var j: Int = 1;
			while (j <= m)
			{
				if (text.charAt(i - 1) == sequence.charAt(j - 1))
				{
					// Change element value by using sum of top two elements
					dp(i)(j) = dp(i - 1)(j - 1) + dp(i - 1)(j);
				}
				else
				{
					dp(i)(j) = dp(i - 1)(j);
				}
				j += 1;
			}
			i += 1;
		}
		// Display calculated result
		println(dp(n)(m));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		var text: String = "aaabbb";
		var sequence: String = "ab";
		/*
		    text = aaabbb
		    -------------
		    subsequence = ab
		    
		        a a a b b b
		    ➀   -     -    ->ab
		        a a a b b b
		    ➁   -       -   ->ab
		        a a a b b b
		    ➂   -         - ->ab
		        a a a b b b
		    ➃     -   -     ->ab
		        a a a b b b
		    ➄     -     -   ->ab
		        a a a b b b
		    ➅     -       - ->ab
		        a a a b b b
		    ➆       - -     ->ab
		        a a a b b b
		    ➇       -   -   ->ab 
		        a a a b b b            
		    ➈       -     - ->ab 
		    ______________________
		    Result = 9
		*/
		task.countSubSequence(text, sequence);
	}
}

Output

9
import Foundation;
/*
    Swift 4 program for
    Find the frequency of subsequence in given string
*/
class Subsequence
{
	func countSubSequence(_ t: String, _ s: String)
	{
      	let text = Array(t);
      	let sequence = Array(s);
		// Get the length of given parameters
		let n: Int = text.count;
		let m: Int = sequence.count;
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
		var i: Int = 1;
		// Set initial value of first column
		while (i <= n)
		{
			dp[i][0] = 1;
			i += 1;
		}
		i = 1;
		// Set initial value of first row
		while (i <= m)
		{
			dp[0][i] = 0;
			i += 1;
		}
		// Active first row first column
		dp[0][0] = 1;
		i = 1;
		while (i <= n)
		{
			var j: Int = 1;
			while (j <= m)
			{
				if (text[i - 1] == sequence[j - 1])
				{
					// Change element value by using sum of top two elements
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				}
				else
				{
					dp[i][j] = dp[i - 1][j];
				}
				j += 1;
			}
			i += 1;
		}
		// Display calculated result
		print(dp[n][m]);
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	let text: String = "aaabbb";
	let sequence: String = "ab";
	/*
	    text = aaabbb
	    -------------
	    subsequence = ab
	    
	        a a a b b b
	    ➀   -     -    ->ab
	        a a a b b b
	    ➁   -       -   ->ab
	        a a a b b b
	    ➂   -         - ->ab
	        a a a b b b
	    ➃     -   -     ->ab
	        a a a b b b
	    ➄     -     -   ->ab
	        a a a b b b
	    ➅     -       - ->ab
	        a a a b b b
	    ➆       - -     ->ab
	        a a a b b b
	    ➇       -   -   ->ab 
	        a a a b b b            
	    ➈       -     - ->ab 
	    ______________________
	    Result = 9
	*/
	task.countSubSequence(text, sequence);
}
main();

Output

9
/*
    Kotlin program for
    Find the frequency of subsequence in given string
*/
class Subsequence
{
	fun countSubSequence(text: String, sequence: String): Unit
	{
		// Get the length of given parameters
		val n: Int = text.length;
		val m: Int = sequence.length;
		var dp: Array < Array < Int >> = Array(n + 1)
		{
			Array(m + 1)
			{
				0
			}
		};
		var i: Int = 1;
		// Set initial value of first column
		while (i <= n)
		{
			dp[i][0] = 1;
			i += 1;
		}
		i = 1;
		// Set initial value of first row
		while (i <= m)
		{
			dp[0][i] = 0;
			i += 1;
		}
		// Active first row first column
		dp[0][0] = 1;
		i = 1;
		while (i <= n)
		{
			var j: Int = 1;
			while (j <= m)
			{
				if (text.get(i - 1) == sequence.get(j - 1))
				{
					// Change element value by using sum of top two elements
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				}
				else
				{
					dp[i][j] = dp[i - 1][j];
				}
				j += 1;
			}
			i += 1;
		}
		// Display calculated result
		println(dp[n][m]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	val text: String = "aaabbb";
	val sequence: String = "ab";
	/*
	    text = aaabbb
	    -------------
	    subsequence = ab
	    
	        a a a b b b
	    ➀   -     -    ->ab
	        a a a b b b
	    ➁   -       -   ->ab
	        a a a b b b
	    ➂   -         - ->ab
	        a a a b b b
	    ➃     -   -     ->ab
	        a a a b b b
	    ➄     -     -   ->ab
	        a a a b b b
	    ➅     -       - ->ab
	        a a a b b b
	    ➆       - -     ->ab
	        a a a b b b
	    ➇       -   -   ->ab 
	        a a a b b b            
	    ➈       -     - ->ab 
	    ______________________
	    Result = 9
	*/
	task.countSubSequence(text, sequence);
}

Output

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