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 approachclass GFG{// Function to find the frequencystatic 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 Codepublic 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 approachimport 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 approachusing System;class GFG{// Function to find the frequencystatic 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 Codepublic 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:
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
