Posted on by Kalkicode
Code Dynamic Programming

Frequency of maximum occurring subsequence in given string

In this article, we will discuss the problem of finding the frequency of the maximum occurring subsequence in a given string. We will explore a Java program that efficiently solves this problem and analyze its time complexity.

Problem Statement:

Given a string consisting of lowercase alphabets, our task is to find the frequency of the maximum occurring subsequence in the given string. A subsequence is a sequence that can be derived from the original string by deleting some or no elements without changing the order of the remaining elements.

Approach and Algorithm:

To solve this problem, we will use dynamic programming and frequency counting techniques. Here is the step-by-step approach:

  1. Initialize a 2D array, 'dp,' of size 26x26 to store the frequencies of subsequences formed by pairs of alphabets. Initialize an array, 'frequency,' of size 26 to store the frequency of each individual alphabet.
  2. Iterate through each character in the input string.
  3. If the character is a lowercase alphabet, proceed; otherwise, return, as the program only works with lowercase alphabets.
  4. For each alphabet encountered, update the frequencies of subsequences in the 'dp' array. If the updated frequency is greater than the current maximum frequency, update the result variable.
  5. Update the frequency of the current alphabet in the 'frequency' array and check if it is greater than the current maximum frequency. If so, update the result variable.
  6. After iterating through the entire string, the result variable will contain the frequency of the maximum occurring subsequence.
  7. Display the calculated result.

Code solution:

/*
    Java program for
    Frequency of maximum occurring subsequence in given string
*/
public class Subsequence
{
	public void maxFrequencySub(String text)
	{
		int n = text.length();
		if (n == 0)
		{
			return;
		}
		// Working with 26 alphabets
		// 'a'-'z'
		int[][] dp = new int[26][26];
		int[] frequency = new int[26];
		int result = 0;
		// Set initial frequency and dp value.
		// And set initial value of elements.
		for (int i = 0; i < 26; ++i)
		{
			for (int j = 0; j < 26; ++j)
			{
				dp[i][j] = 0;
			}
			frequency[i] = 0;
		}
		for (int i = 0; i < n; ++i)
		{
			if (text.charAt(i) >= 'a' && text.charAt(i) <= 'z')
			{
				for (int j = 0; j < 26; ++j)
				{
					dp[j][text.charAt(i) - 'a'] += frequency[j];
					if (dp[j][text.charAt(i) - 'a'] > result)
					{
						result = dp[j][text.charAt(i) - 'a'];
					}
				}
				frequency[text.charAt(i) - 'a'] += 1;
				if (frequency[text.charAt(i) - 'a'] > result)
				{
					result = frequency[text.charAt(i) - 'a'];
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
		}
		// Display calculated result
		System.out.println(result);
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text = "aaabbb";
		/*
		    text = aaabbb
		    -------------
		    ab is max frequency subsequence
		    

		        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.maxFrequencySub(text);
	}
}

Output

9
// Include header file
#include <iostream>

#include <string>

using namespace std;
/*
    C++ program for
    Frequency of maximum occurring subsequence in given string
*/
class Subsequence
{
	public: void maxFrequencySub(string text)
	{
		int n = text.length();
		if (n == 0)
		{
			return;
		}
		// Working with 26 alphabets
		// 'a'-'z'
		int dp[26][26];
		int frequency[26];
		int result = 0;
		// Set initial frequency and dp value.
		// And set initial value of elements.
		for (int i = 0; i < 26; ++i)
		{
			for (int j = 0; j < 26; ++j)
			{
				dp[i][j] = 0;
			}
			frequency[i] = 0;
		}
		for (int i = 0; i < n; ++i)
		{
			if (text[i] >= 'a' && text[i] <= 'z')
			{
				for (int j = 0; j < 26; ++j)
				{
					dp[j][text[i] - 'a'] += frequency[j];
					if (dp[j][text[i] - 'a'] > result)
					{
						result = dp[j][text[i] - 'a'];
					}
				}
				frequency[text[i] - 'a'] += 1;
				if (frequency[text[i] - 'a'] > result)
				{
					result = frequency[text[i] - 'a'];
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
		}
		// Display calculated result
		cout << result << endl;
	}
};
int main()
{
	Subsequence *task = new Subsequence();
	string text = "aaabbb";
	/*
	    text = aaabbb
	    -------------
	    ab is max frequency subsequence
	    
	        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->maxFrequencySub(text);
	return 0;
}

Output

9
// Include namespace system
using System;
/*
    Csharp program for
    Frequency of maximum occurring subsequence in given string
*/
public class Subsequence
{
	public void maxFrequencySub(String text)
	{
		int n = text.Length;
		if (n == 0)
		{
			return;
		}
		// Working with 26 alphabets
		// 'a'-'z'
		int[,] dp = new int[26,26];
		int[] frequency = new int[26];
		int result = 0;
		// Set initial frequency and dp value.
		// And set initial value of elements.
		for (int i = 0; i < 26; ++i)
		{
			for (int j = 0; j < 26; ++j)
			{
				dp[i,j] = 0;
			}
			frequency[i] = 0;
		}
		for (int i = 0; i < n; ++i)
		{
			if (text[i] >= 'a' && text[i] <= 'z')
			{
				for (int j = 0; j < 26; ++j)
				{
					dp[j,text[i] - 'a'] += frequency[j];
					if (dp[j,text[i] - 'a'] > result)
					{
						result = dp[j,text[i] - 'a'];
					}
				}
				frequency[text[i] - 'a'] += 1;
				if (frequency[text[i] - 'a'] > result)
				{
					result = frequency[text[i] - 'a'];
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
		}
		// Display calculated result
		Console.WriteLine(result);
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text = "aaabbb";
		/*
		    text = aaabbb
		    -------------
		    ab is max frequency subsequence
		    
		        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.maxFrequencySub(text);
	}
}

Output

9
package main
import "fmt"
/*
    Go program for
    Frequency of maximum occurring subsequence in given string
*/

func maxFrequencySub(text string) {
	var n int = len(text)
	if n == 0 {
		return
	}
	// Working with 26 alphabets
	// 'a'-'z'
	var dp = make([][] int, 26)
	for i:= 0; i < 26; i++{
		dp[i] = make([]int,26)
	}
	var frequency = make([] int, 26)
	var result int = 0
	// Set initial frequency and dp value.
	// And set initial value of elements.
	for i := 0 ; i < 26 ; i++ {
		for j := 0 ; j < 26 ; j++ {
			dp[i][j] = 0
		}
		frequency[i] = 0
	}
	for i := 0 ; i < n ; i++ {
		if text[i] >= 'a' && text[i] <= 'z' {
			for j := 0 ; j < 26 ; j++ {
				dp[j][text[i] - 'a'] += frequency[j]
				if dp[j][text[i] - 'a'] > result {
					result = dp[j][text[i] - 'a']
				}
			}
			frequency[text[i] - 'a'] += 1
			if frequency[text[i] - 'a'] > result {
				result = frequency[text[i] - 'a']
			}
		} else {
			// This program are work on 'a'-'z' alphabet character.
			// And given text are include different alphabet character
			return
		}
	}
	// Display calculated result
	fmt.Println(result)
}
func main() {

	var text string = "aaabbb"
	/*
	    text = aaabbb
	    -------------
	    ab is max frequency subsequence
	    
	        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
	*/
	maxFrequencySub(text)
}

Output

9
<?php
/*
    Php program for
    Frequency of maximum occurring subsequence in given string
*/
class Subsequence
{
	public	function maxFrequencySub($text)
	{
		$n = strlen($text);
		if ($n == 0)
		{
			return;
		}
		// Working with 26 alphabets
		// 'a'-'z'.
		// Set initial frequency and dp value.
		// And set initial value of elements.
		$dp = array_fill(0, 26, array_fill(0, 26, 0));
		$frequency = array_fill(0, 26, 0);
		$result = 0;
		for ($i = 0; $i < $n; ++$i)
		{
			if ($text[$i] >= 'a' && $text[$i] <= 'z')
			{
				for ($j = 0; $j < 26; ++$j)
				{
					$dp[$j][ord($text[$i]) - ord('a')] += $frequency[$j];
					if ($dp[$j][ord($text[$i]) - ord('a')] > $result)
					{
						$result = $dp[$j][ord($text[$i]) - ord('a')];
					}
				}
				$frequency[ord($text[$i]) - ord('a')] += 1;
				if ($frequency[ord($text[$i]) - ord('a')] > $result)
				{
					$result = $frequency[ord($text[$i]) - ord('a')];
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
		}
		// Display calculated result
		echo($result.
			"\n");
	}
}

function main()
{
	$task = new Subsequence();
	$text = "aaabbb";
	/*
	    text = aaabbb
	    -------------
	    ab is max frequency subsequence
	    
	        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->maxFrequencySub($text);
}
main();

Output

9
/*
    Node JS program for
    Frequency of maximum occurring subsequence in given string
*/
class Subsequence
{
	maxFrequencySub(text)
	{
		var n = text.length;
		if (n == 0)
		{
			return;
		}
		// Working with 26 alphabets
		// 'a'-'z'.
		// Set initial frequency and dp value.
		// And set initial value of elements.
		var dp = Array(26).fill(0).map(() => new Array(26).fill(0));
		var frequency = Array(26).fill(0);
		var result = 0;
		for (var i = 0; i < n; ++i)
		{
			if (text.charAt(i) >= 'a' && text.charAt(i) <= 'z')
			{
				for (var j = 0; j < 26; ++j)
				{
					dp[j][text.charAt(i).charCodeAt(0) - 
                          'a'.charCodeAt(0)] += frequency[j];
					if (dp[j][text.charAt(i).charCodeAt(0) - 
                              'a'.charCodeAt(0)] > result)
					{
						result = dp[j][text.charAt(i).charCodeAt(0) -
                                       'a'.charCodeAt(0)];
					}
				}
				frequency[text.charAt(i).charCodeAt(0) - 
                          'a'.charCodeAt(0)] += 1;
				if (frequency[text.charAt(i).charCodeAt(0) - 
                              'a'.charCodeAt(0)] > result)
				{
					result = frequency[text.charAt(i).charCodeAt(0) -
                                       'a'.charCodeAt(0)];
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
		}
		// Display calculated result
		console.log(result);
	}
}

function main()
{
	var task = new Subsequence();
	var text = "aaabbb";
	/*
	    text = aaabbb
	    -------------
	    ab is max frequency subsequence
	    
	        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.maxFrequencySub(text);
}
main();

Output

9
#    Python 3 program for
#    Frequency of maximum occurring subsequence in given string
class Subsequence :
	def maxFrequencySub(self, text) :
		n = len(text)
		if (n == 0) :
			return
		
		#  Working with 26 alphabets
		#  'a'-'z'.
		#  Set initial frequency and dp value.
		#  And set initial value of elements.
		dp = [[0] * (26) for _ in range(26) ]
		frequency = [0] * (26)
		result = 0
		i = 0
		while (i < n) :
			if (text[i] >= 'a'
				and text[i] <= 'z') :
				j = 0
				while (j < 26) :
					dp[j][ord(text[i]) - ord('a')] += frequency[j]
					if (dp[j][ord(text[i]) - ord('a')] > result) :
						result = dp[j][ord(text[i]) - ord('a')]
					
					j += 1
				
				frequency[ord(text[i]) - ord('a')] += 1
				if (frequency[ord(text[i]) - ord('a')] > result) :
					result = frequency[ord(text[i]) - ord('a')]
				
			else :
				#  This program are work on 'a'-'z' alphabet character.
				#  And given text are include different alphabet character
				return
			
			i += 1
		
		#  Display calculated result
		print(result)
	

def main() :
	task = Subsequence()
	text = "aaabbb"
	#    text = aaabbb
	#    -------------
	#    ab is max frequency subsequence
	#        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.maxFrequencySub(text)

if __name__ == "__main__": main()

Output

9
#    Ruby program for
#    Frequency of maximum occurring subsequence in given string
class Subsequence 
	def maxFrequencySub(text) 
		n = text.length
		if (n == 0) 
			return
		end

		#  Working with 26 alphabets
		#  'a'-'z'.
		#  Set initial frequency and dp value.
		#  And set initial value of elements.
		dp = Array.new(26) {Array.new(26) {0}}
		frequency = Array.new(26) {0}
		result = 0
		i = 0
		while (i < n) 
			if (text[i] >= 'a' && text[i] <= 'z') 
				j = 0
				while (j < 26) 
					dp[j][text[i].ord - 'a'.ord] += frequency[j]
					if (dp[j][text[i].ord - 'a'.ord] > result) 
						result = dp[j][text[i].ord - 'a'.ord]
					end

					j += 1
				end

				frequency[text[i].ord - 'a'.ord] += 1
				if (frequency[text[i].ord - 'a'.ord] > result) 
					result = frequency[text[i].ord - 'a'.ord]
				end

			else
 
				#  This program are work on 'a'-'z' alphabet character.
				#  And given text are include different alphabet character
				return
			end

			i += 1
		end

		#  Display calculated result
		print(result, "\n")
	end

end

def main() 
	task = Subsequence.new()
	text = "aaabbb"
	#    text = aaabbb
	#    -------------
	#    ab is max frequency subsequence
	#        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.maxFrequencySub(text)
end

main()

Output

9
import scala.collection.mutable._;
/*
    Scala program for
    Frequency of maximum occurring subsequence in given string
*/
class Subsequence()
{
	def maxFrequencySub(text: String): Unit = {
		var n: Int = text.length();
		if (n == 0)
		{
			return;
		}
		// Working with 26 alphabets
		// 'a'-'z'.
		// Set initial frequency and dp value.
		// And set initial value of elements.
		var dp: Array[Array[Int]] = Array.fill[Int](26, 26)(0);
		var frequency: Array[Int] = Array.fill[Int](26)(0);
		var result: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			if (text.charAt(i) >= 'a' && text.charAt(i) <= 'z')
			{
				var j: Int = 0;
				while (j < 26)
				{
					dp(j)(text.charAt(i).toInt - 'a'.toInt) += frequency(j);
					if (dp(j)(text.charAt(i).toInt - 'a'.toInt) > result)
					{
						result = dp(j)(text.charAt(i).toInt - 'a'.toInt);
					}
					j += 1;
				}
				frequency(text.charAt(i).toInt - 'a'.toInt) += 1;
				if (frequency(text.charAt(i).toInt - 'a'.toInt) > result)
				{
					result = frequency(text.charAt(i).toInt - 'a'.toInt);
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
			i += 1;
		}
		// Display calculated result
		println(result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		var text: String = "aaabbb";
		/*
		    text = aaabbb
		    -------------
		    ab is max frequency subsequence
		    
		        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.maxFrequencySub(text);
	}
}

Output

9
import Foundation;
/*
    Swift 4 program for
    Frequency of maximum occurring subsequence in given string
*/
class Subsequence
{
	func maxFrequencySub(_ data: String)
	{
      	let text = Array(data);
		let n: Int = text.count;
		if (n == 0)
		{
			return;
		}
      	
		// Working with 26 alphabets
		// 'a'-'z'.
		// Set initial frequency and dp value.
		// And set initial value of elements.
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: 26), count: 26);
		var frequency: [Int] = Array(repeating: 0, count: 26);
		var result: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			if (text[i] >= "a" && text[i] <= "z")
			{
				var j: Int = 0;
				while (j < 26)
				{
					dp[j][Int(UnicodeScalar(String(text[i]))!.value) -
                          Int(UnicodeScalar(String("a"))!.value)] += frequency[j];
					if (dp[j][Int(UnicodeScalar(String(text[i]))!.value) -
                              Int(UnicodeScalar(String("a"))!.value)] > result)
					{
						result = dp[j][Int(UnicodeScalar(String(text[i]))!.value) - Int(UnicodeScalar(String("a"))!.value)];
					}
					j += 1;
				}
				frequency[Int(UnicodeScalar(String(text[i]))!.value) -
                          Int(UnicodeScalar(String("a"))!.value)] += 1;
				if (frequency[Int(UnicodeScalar(String(text[i]))!.value) -
                              Int(UnicodeScalar(String("a"))!.value)] > 
                    result)
				{
					result = frequency[Int(UnicodeScalar(String(text[i]))!.value) - 
                                       Int(UnicodeScalar(String("a"))!.value)];
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
			i += 1;
		}
		// Display calculated result
		print(result);
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	let text: String = "aaabbb";
	/*
	    text = aaabbb
	    -------------
	    ab is max frequency subsequence
	    
	        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.maxFrequencySub(text);
}
main();

Output

9
/*
    Kotlin program for
    Frequency of maximum occurring subsequence in given string
*/
class Subsequence
{
	fun maxFrequencySub(text: String): Unit
	{
		val n: Int = text.length;
		if (n == 0)
		{
			return;
		}
		// Working with 26 alphabets
		// 'a'-'z'
		var dp: Array < Array < Int >> = Array(26)
		{
			Array(26)
			{
				0
			}
		};
		var frequency: Array < Int > = Array(26)
		{
			0
		};
		var result: Int = 0;
		var i: Int = 0;
		// Set initial frequency and dp value.
		// And set initial value of elements.
		while (i < 26)
		{
			var j: Int = 0;
			while (j < 26)
			{
				dp[i][j] = 0;
				j += 1;
			}
			frequency[i] = 0;
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			if (text.get(i) >= 'a' && text.get(i) <= 'z')
			{
				var j: Int = 0;
				while (j < 26)
				{
					dp[j][text.get(i).toInt() - 'a'.toInt()] += frequency[j];
					if (dp[j][text.get(i).toInt() - 'a'.toInt()] > result)
					{
						result = dp[j][text.get(i).toInt() - 'a'.toInt()];
					}
					j += 1;
				}
				frequency[text.get(i).toInt() - 'a'.toInt()] += 1;
				if (frequency[text.get(i).toInt() - 'a'.toInt()] > result)
				{
					result = frequency[text.get(i).toInt() - 'a'.toInt()];
				}
			}
			else
			{
				// This program are work on 'a'-'z' alphabet character.
				// And given text are include different alphabet character
				return;
			}
			i += 1;
		}
		// Display calculated result
		println(result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	val text: String = "aaabbb";
	/*
	    text = aaabbb
	    -------------
	    ab is max frequency subsequence
	    
	        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.maxFrequencySub(text);
}

Output

9

Java Code Explanation:

The provided Java code implements the above algorithm to solve the problem. Here is a breakdown of the code:

  1. The class 'Subsequence' contains a method named 'maxFrequencySub' that takes the input string as a parameter and returns void.
  2. The code initializes the necessary variables and arrays.
  3. The program iterates through each character in the string and performs the required calculations.
  4. Finally, the result is printed using the 'System.out.println' statement.
  5. The main method creates an instance of the 'Subsequence' class, sets the input string, and calls the 'maxFrequencySub' method.

Example:

Let's consider the input string "aaabbb" to understand how the program calculates the frequency of the maximum occurring subsequence.

The string "aaabbb" has multiple occurrences of the subsequence "ab." The program calculates the frequency of this subsequence by considering all possible combinations of "a" and "b" characters.

By following the step-by-step execution of the program, we find that the frequency of the maximum occurring subsequence is 9.

Time Complexity Analysis:

The time complexity of the given solution is O(n), where 'n' represents the length of the input string. This is because we iterate through each character in the string once and perform constant-time operations for each character.

we discussed the problem of finding the frequency of the maximum occurring subsequence in a given string. We presented a Java program that efficiently solves this problem using dynamic programming and frequency counting techniques. We also provided an example and analyzed the time complexity of the solution. By understanding and implementing this approach, you can easily determine the frequency of the maximum occurring subsequence in any given string.

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