Conteo de la subsecuencia máxima que ocurre usando solo aquellos caracteres cuyos índices están en GP

Dada una string S , la tarea es encontrar el conteo de la subsecuencia máxima que ocurre P desde S usando solo aquellos caracteres cuyos índices están en progresión geométrica .
Nota: Considere la indexación basada en 1 en S.

Ejemplos: 

Entrada: S = “ddee”
Salida: 4
Explicación: 
Si tomamos P = “de”, entonces P aparece 4 veces en S. { {1, 3}, {1, 4}, {2, 3}, {2 , 4} }

Entrada: S = “geeksforgeeks”
Salida: 6
Explicación: 
Si tomamos P = “ek”, entonces P aparece 6 veces en S. { {2, 4}, {3, 4}, {2, 12} {3, 12}, {10, 12}, {11, 12} }

Enfoque ingenuo: la idea es generar todas las subsecuencias posibles de la string dada de modo que los índices de la string deben estar en progresión geométrica . Ahora, para cada subsecuencia generada, encuentre la ocurrencia de cada subsecuencia e imprima el máximo entre esas ocurrencias.

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque Eficiente: La idea es observar que cualquier subsecuencia P puede tener cualquier longitud . Digamos que si P = “abc” y ocurre 10 veces en S (donde “abc” tiene su índice en GP en S), entonces podemos ver que la subsecuencia “ab” (que tiene índice en GP) también ocurrirá 10 veces en S. Entonces, para simplificar la solución, la posible longitud de P será menor que igual a 2. A continuación se muestran los pasos:

1. Es necesario elegir la subsecuencia P de longitud mayor que 1 porque P de longitud mayor que 1 ocurrirá mucho más tiempo que de longitud uno si S no contiene solo caracteres únicos.
2. Para longitud 1 cuente la frecuencia de cada alfabeto en la string .
3. 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) .
4. 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).

1. 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>
using namespace std;
 
// Function to count maximum occurring
// subsequence using only those characters
// whose indexes are in GP
int findMaxTimes(string S)
{
    long long int arr[26];
    long long int dp[26][26];
 
    // Initialize 1-D array and 2-D
    // dp array to 0
    memset(arr, 0, sizeof(arr));
    memset(dp, 0, sizeof(dp));
 
    // Iterate till the length of
    // the given string
    for (int i = 0; i < S.size(); i++) {
        int now = S[i] - 'a';
        for (int j = 0; j < 26; j++) {
            dp[j][now] += arr[j];
        }
        arr[now]++;
    }
 
    long long int ans = 0;
 
    // Update ans for 1-length subsequence
    for (int i = 0; i < 26; i++)
        ans = max(ans, arr[i]);
 
    // Update ans for 2-length subsequence
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            ans = max(ans, dp[i][j]);
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    // Given string s
    string S = "ddee";
 
    // Function Call
    cout << findMaxTimes(S);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count maximum occurring
// subsequence using only those characters
// whose indexes are in GP
static int findMaxTimes(String S)
{
    int []arr = new int[26];
    int [][]dp = new int[26][26];
 
    // Iterate till the length of
    // the given String
    for(int i = 0; i < S.length(); i++)
    {
        int now = S.charAt(i) - 'a';
        for(int j = 0; j < 26; j++)
        {
            dp[j][now] += arr[j];
        }
        arr[now]++;
    }
 
    int ans = 0;
 
    // Update ans for 1-length subsequence
    for(int i = 0; i < 26; i++)
        ans = Math.max(ans, arr[i]);
 
    // Update ans for 2-length subsequence
    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < 26; j++)
        {
            ans = Math.max(ans, dp[i][j]);
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given String s
    String S = "ddee";
 
    // Function call
    System.out.print(findMaxTimes(S));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to count maximum occurring
# subsequence using only those characters
# whose indexes are in GP
def findMaxTimes(S):
 
    # Initialize 1-D array and 2-D
    # dp array to 0
    arr = [0] * 26
    dp = [[0 for x in range(26)]
             for y in range(26)]
 
    # Iterate till the length of
    # the given string
    for i in range(len(S)):
        now = ord(S[i]) - ord('a')
         
        for j in range(26):
            dp[j][now] += arr[j]
 
        arr[now] += 1
 
    ans = 0
 
    # Update ans for 1-length subsequence
    for i in range(26):
        ans = max(ans, arr[i])
 
    # Update ans for 2-length subsequence
    for i in range(26):
        for j in range(26):
            ans = max(ans, dp[i][j])
 
    # Return the answer
    return ans
 
# Driver Code
 
# Given string s
S = "ddee"
 
# Function call
print(findMaxTimes(S))
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
class GFG{
 
// Function to count maximum occurring
// subsequence using only those characters
// whose indexes are in GP
static int findMaxTimes(String S)
{
    int []arr = new int[26];
    int [,]dp = new int[26, 26];
 
    // Iterate till the length of
    // the given String
    for(int i = 0; i < S.Length; i++)
    {
        int now = S[i] - 'a';
        for(int j = 0; j < 26; j++)
        {
            dp[j, now] += arr[j];
        }
        arr[now]++;
    }
 
    int ans = 0;
 
    // Update ans for 1-length subsequence
    for(int i = 0; i < 26; i++)
        ans = Math.Max(ans, arr[i]);
 
    // Update ans for 2-length subsequence
    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < 26; j++)
        {
            ans = Math.Max(ans, dp[i, j]);
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given String s
    String S = "ddee";
 
    // Function call
    Console.Write(findMaxTimes(S));
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program for the above approach
 
// Function to count maximum occurring
// subsequence using only those characters
// whose indexes are in GP
function findMaxTimes(S)
{
    var arr = Array(26).fill(0);
    var dp = Array.from(Array(26), ()=>Array(26).fill(0));
 
    // Iterate till the length of
    // the given string
    for (var i = 0; i < S.length; i++)
    {
        var now = S[i].charCodeAt(0) - 'a'.charCodeAt(0);
        for (var j = 0; j < 26; j++)
        {
            dp[j][now] += arr[j];
        }
        arr[now]++;
    }
 
    var ans = 0;
 
    // Update ans for 1-length subsequence
    for (var i = 0; i < 26; i++)
        ans = Math.max(ans, arr[i]);
 
    // Update ans for 2-length subsequence
    for (var i = 0; i < 26; i++)
    {
        for (var j = 0; j < 26; j++)
        {
            ans = Math.max(ans, dp[i][j]);
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
// Given string s
var S = "ddee";
 
// Function Call
document.write( findMaxTimes(S));
 
// This code is contributed by noob2000.
</script>

4

Complejidad de tiempo: O(max(N*26, 26 * 26))
Espacio auxiliar: O(26 * 26)