Frecuencia de la subsecuencia máxima que ocurre en una string dada

Dada una string str de alfabetos ingleses en minúsculas, nuestra tarea es encontrar la frecuencia de ocurrencia de una subsecuencia de la string que ocurre el máximo de veces.

Ejemplos:

Entrada: s = “aba” 
Salida: 2 
Explicación: 
Para “aba”, la subsecuencia “ab” ocurre el máximo de veces en la subsecuencia ‘ab’ y ‘aba’.

Entrada: s = “acbab” 
Salida: 3 
Explicación: 
Para “acbab”, “ab” aparece 3 veces, que es el máximo.

Planteamiento: El problema se puede resolver usando Programación Dinámica . Para resolver el problema mencionado anteriormente, la observación clave es que la subsecuencia resultante será de longitud 1 o 2 porque la frecuencia de cualquier subsecuencia de longitud > 2 será menor que la subsecuencia de longitud 1 o 2 , ya que también están presentes en subsecuencias de mayor longitud . . Entonces necesitamos verificar la subsecuencia de longitud 1 o 2 solamente. A continuación se muestran los pasos:

• Para longitud 1 cuente la frecuencia de cada alfabeto en la string.
• Para la longitud 2, forme una array 2D dp[26][26] , donde dp[i][j] indica la frecuencia de la string de char(‘a’ + i) + char(‘a’ + j) .
• La relación de recurrencia que se utiliza en el paso 2 viene dada por:

 dp[i][j] = dp[i][j] + freq[i] 
donde, 
freq[i] = frecuencia del carácter char(‘a’ + i) 
dp[i][j] = frecuencia de la string formada por carácter_actual + char(‘a’ + i).

• El máximo de la array de frecuencias y la array dp[][] da el recuento máximo de cualquier subsecuencia en la string dada.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

<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>

3

Complejidad de tiempo: O(26*N) , donde N es la longitud de la string dada.