Frequency of maximum occurring subsequence in given string

0 0 5 minutes read

Given a string str of lowercase English alphabets, our task is to find the frequency of occurrence a subsequence of the string which occurs the maximum times.

Examples:

Input: s = “aba”
Output: 2
Explanation:
For “aba”, subsequence “ab” occurs maximum times in subsequence ‘ab’ and ‘aba’.

Input: s = “acbab”
Output: 3
Explanation:
For “acbab”, “ab” occurs 3 times which is the maximum.

Approach: The problem can be solved using Dynamic Programming. To solve the problem mentioned above the key observation is that the resultant subsequence will be of length 1 or 2 because frequency of any subsequence of length > 2 will be lower than the subsequence of length 1 or 2 as they are also present in higher length subsequences. So we need to check for the subsequence of length 1 or 2 only. Below are the steps:

For length 1 count the frequency of each alphabet in the string.
For length 2 form a 2D array dp[26][26], where dp[i][j] tells frequency of string of char(‘a’ + i) + char(‘a’ + j).
The recurrence relation is used in the step 2 is given by:

dp[i][j] = dp[i][j] + freq[i]
where,
freq[i] = frequency of character char(‘a’ + i)
dp[i][j] = frequency of string formed by current_character + char(‘a’ + i).

The maximum of frequency array and array dp[][] gives the maximum count of any subsequence in the given string.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
#define ll long long 
using namespace std; 
 
// Function to find the frequency 
ll findCount(string s) 
{ 
    // freq stores frequency of each 
    // english lowercase character 
    ll freq[26]; 
 
    // dp[i][j] stores the count of 
    // subsequence with 'a' + i 
    // and 'a' + j character 
    ll dp[26][26]; 
 
    memset(freq, 0, sizeof freq); 
 
    // Initialize dp to 0 
    memset(dp, 0, sizeof dp); 
 
    for (int i = 0; i < s.size(); ++i) { 
 
        for (int j = 0; j < 26; j++) { 
 
            // Increment the count of 
            // subsequence j and s[i] 
            dp[j][s[i] - 'a'] += freq[j]; 
        } 
 
        // Update the frequency array 
        freq[s[i] - 'a']++; 
    } 
 
    ll ans = 0; 
 
    // For 1 length subsequence 
    for (int i = 0; i < 26; i++) 
        ans = max(freq[i], ans); 
 
    // For 2 length subsequence 
    for (int i = 0; i < 26; i++) { 
        for (int j = 0; j < 26; j++) { 
 
            ans = max(dp[i][j], ans); 
        } 
    } 
 
    // Return the final result 
    return ans; 
} 
 
// Driver Code 
int main() 
{ 
    // Given string str 
    string str = "acbab"; 
 
    // Function Call 
    cout << findCount(str); 
 
    return 0; 
} 

Java

// Java program for the above approach
class GFG{
 
// Function to find the frequency
static int findCount(String s)
{
     
    // freq stores frequency of each
    // english lowercase character
    int []freq = new int[26];
 
    // dp[i][j] stores the count of
    // subsequence with 'a' + i 
    // and 'a' + j character 
    int [][]dp = new int[26][26];
 
    for(int i = 0; i < s.length(); ++i) 
    {
        for(int j = 0; j < 26; j++)
        {
 
            // Increment the count of
            // subsequence j and s[i]
            dp[j][s.charAt(i) - 'a'] += freq[j];
        }
 
        // Update the frequency array
        freq[s.charAt(i) - 'a']++;
    }
 
    int ans = 0;
 
    // For 1 length subsequence
    for(int i = 0; i < 26; i++)
        ans = Math.max(freq[i], ans);
 
    // For 2 length subsequence
    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < 26; j++) 
        {
            ans = Math.max(dp[i][j], ans);
        }
    }
 
    // Return the final result
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given String str
    String str = "acbab";
 
    // Function call
    System.out.print(findCount(str));
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program for the above approach
import numpy
 
# Function to find the frequency 
def findCount(s):
 
    # freq stores frequency of each 
    # english lowercase character 
    freq = [0] * 26
 
    # dp[i][j] stores the count of 
    # subsequence with 'a' + i 
    # and 'a' + j character 
    dp = [[0] * 26] * 26
     
    freq = numpy.zeros(26)
    dp = numpy.zeros([26, 26])
 
    for i in range(0, len(s)): 
        for j in range(26): 
 
            # Increment the count of 
            # subsequence j and s[i] 
            dp[j][ord(s[i]) - ord('a')] += freq[j] 
         
        # Update the frequency array 
        freq[ord(s[i]) - ord('a')] += 1
 
    ans = 0
 
    # For 1 length subsequence 
    for i in range(26): 
        ans = max(freq[i], ans)
         
    # For 2 length subsequence 
    for i in range(0, 26): 
        for j in range(0, 26): 
            ans = max(dp[i][j], ans) 
     
    # Return the final result 
    return int(ans) 
 
# Driver Code 
 
# Given string str 
str = "acbab"
 
# Function call 
print(findCount(str))
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the frequency
static int findCount(String s)
{
     
    // freq stores frequency of each
    // english lowercase character
    int []freq = new int[26];
 
    // dp[i,j] stores the count of
    // subsequence with 'a' + i 
    // and 'a' + j character 
    int [,]dp = new int[26, 26];
 
    for(int i = 0; i < s.Length; ++i) 
    {
        for(int j = 0; j < 26; j++)
        {
 
            // Increment the count of
            // subsequence j and s[i]
            dp[j, s[i] - 'a'] += freq[j];
        }
 
        // Update the frequency array
        freq[s[i] - 'a']++;
    }
 
    int ans = 0;
 
    // For 1 length subsequence
    for(int i = 0; i < 26; i++)
        ans = Math.Max(freq[i], ans);
 
    // For 2 length subsequence
    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < 26; j++) 
        {
            ans = Math.Max(dp[i, j], ans);
        }
    }
 
    // Return the readonly result
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given String str
    String str = "acbab";
 
    // Function call
    Console.Write(findCount(str));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for the above approach 
 
// Function to find the frequency 
function findCount(s) 
{ 
    // freq stores frequency of each 
    // english lowercase character 
    var freq = Array(26).fill(0);
 
    // dp[i][j] stores the count of 
    // subsequence with 'a' + i 
    // and 'a' + j character 
    var dp = Array.from(Array(26), ()=>Array(26).fill(0));
 
    for (var i = 0; i < s.length; ++i) { 
 
        for (var j = 0; j < 26; j++) { 
 
            // Increment the count of 
            // subsequence j and s[i] 
            dp[j][s[i].charCodeAt(0) - 
            'a'.charCodeAt(0)] += freq[j]; 
        } 
 
        // Update the frequency array 
        freq[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; 
    } 
 
    var ans = 0; 
 
    // For 1 length subsequence 
    for (var i = 0; i < 26; i++) 
        ans = Math.max(freq[i], ans); 
 
    // For 2 length subsequence 
    for (var i = 0; i < 26; i++) { 
        for (var j = 0; j < 26; j++) { 
 
            ans = Math.max(dp[i][j], ans); 
        } 
    } 
 
    // Return the final result 
    return ans; 
} 
 
// Driver Code 
 
// Given string str 
var str = "acbab"; 
 
// Function Call 
document.write( findCount(str)); 
 
</script>

Output:

Time Complexity: O(26*N), where N is the length of the given string.
Auxiliary Space: O(M), where M = 26*26

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!