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:
- 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.
- Iterate through each character in the input string.
- If the character is a lowercase alphabet, proceed; otherwise, return, as the program only works with lowercase alphabets.
- 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.
- 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.
- After iterating through the entire string, the result variable will contain the frequency of the maximum occurring subsequence.
- 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
9package 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
9import 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
9Java Code Explanation:
The provided Java code implements the above algorithm to solve the problem. Here is a breakdown of the code:
- The class 'Subsequence' contains a method named 'maxFrequencySub' that takes the input string as a parameter and returns void.
- The code initializes the necessary variables and arrays.
- The program iterates through each character in the string and performs the required calculations.
- Finally, the result is printed using the 'System.out.println' statement.
- 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.
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