Maximice el recuento de subsecuencias palindrómicas de 3 longitudes con cada parte de índice de una sola subsecuencia

Dada una string , S , la tarea es encontrar el número máximo de subsecuencias palindrómicas indexadas distintas de longitud 3 posibles de la string dada.

Ejemplos:

Entrada : str = “geekforg”
Salida : 2
Explicación: Las posibles subsecuencias palindrómicas de longitud 3 que satisfacen las condiciones son “gkg” y “efe”. Por lo tanto, la salida requerida es 2.

Entrada: str = “geek” 
Salida: 1
Explicación: Las posibles subsecuencias palindrómicas de longitud 3 que satisfacen las condiciones son “ege” .

Enfoque: La idea es contar la frecuencia de cada carácter de la string S , y contar los pares de frecuencia de modo que los pares sean de los mismos caracteres y contar el número de subsecuencias de longitud 3 dividiendo la string S por 3 . Finalmente, imprima el mínimo de pares de frecuencias como el número de subsecuencias. Siga los pasos a continuación para resolver el problema:

• Inicialice una array, digamos freq[] , para almacenar las frecuencias de cada carácter de la string S .
• Inicialice una variable, digamos freqPair , para almacenar los pares de frecuencia que tienen pares de los mismos caracteres.
• Inicialice una variable, digamos len , para almacenar el número de subsecuencias de longitud 3 de la string S .
• Iterar sobre el rango [0, str.length() – 1] . Por cada i ^-ésimo índice de la string S , incremente la cuenta del carácter freq[S[i] – ‘a’] en 1 .
• Iterar sobre el rango [0, 26] . Para cada i ^-ésimo índice de la array freq[], cuente los pares de frecuencia dividiendo el elemento de la array por 2 .
• Finalmente, imprima el valor del mínimo de freqPair y len .

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the maximum number
// oaf palindrome subsequences of length 3
// considering the same index only once
int maxNumPalindrome(string S)
{
 
    // Index of the string S
    int i = 0;
 
    // Stores the frequency of
    // every character
    int freq[26] = { 0 };
 
    // Stores the pair of frequency
    // containing same characters
    int freqPair = 0;
 
    // Number of subsequences
    // having length 3
    int len = S.length() / 3;
 
    // Counts the frequency
    while (i < S.length()) {
 
        freq[S[i] - 'a']++;
        i++;
    }
 
    // Counts the pair of frequency
    for (i = 0; i < 26; i++) {
 
        freqPair += (freq[i] / 2);
    }
 
    // Returns the minimum value
    return min(freqPair, len);
}
 
// Driver Code
int main()
{
 
    string S = "geeksforg";
 
    cout << maxNumPalindrome(S) << endl;
 
    return 0;
}

// Java program to implement
// the above approach
 
import java.util.*;
 
class GFG {
   
    // Driver Code
    public static void main(String[] args)
    {
 
        String S = "geeksforg";
 
        System.out.println(maxNumPalindrome(S));
    }
 
    // Function to count the maximum number
    // of palindrome subsequences of length 3
    // considering the same index only once
    static int maxNumPalindrome(String S)
    {
 
        // Index of the string S
        int i = 0;
 
        // Stores the frequency of
        // every character
        int[] freq = new int[26];
 
        // Stores the pair of frequency
        // containing same characters
        int freqPair = 0;
 
        // Number of subsequences
        // having length 3
        int len = S.length() / 3;
 
        // Counts the frequency
        while (i < S.length()) {
 
            freq[S.charAt(i) - 'a']++;
            i++;
        }
 
        // Counts the pair of frequency
        for (i = 0; i < 26; i++) {
 
            freqPair += (freq[i] / 2);
        }
 
        // Returns the minimum value
        return Math.min(freqPair, len);
    }
}

# Python3 program to implement
# the above approach
 
# Function to count the maximum number
# of palindrome subsequences of length 3
# considering the same index only once
def maxNumPalindrome(S):
     
    # Index of the S
    i = 0
 
    # Stores the frequency of
    # every character
    freq = [0] * 26
 
    # Stores the pair of frequency
    # containing same characters
    freqPair = 0
 
    # Number of subsequences
    # having length 3
    ln = len(S) // 3
 
    # Counts the frequency
    while (i < len(S)):
        freq[ord(S[i]) - ord('a')] += 1
        i += 1
 
    # Counts the pair of frequency
    for i in range(26):
        freqPair += (freq[i] // 2)
 
    # Returns the minimum value
    return min(freqPair, ln)
 
# Driver Code
if __name__ == '__main__':
 
    S = "geeksforg"
 
    print(maxNumPalindrome(S))
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach 
using System;
class GFG
{
   
    // Driver Code
    public static void Main(String[] args)
    {
        string S = "geeksforg";
        Console.WriteLine(maxNumPalindrome(S));
    }
 
    // Function to count the maximum number
    // of palindrome subsequences of length 3
    // considering the same index only once
    static int maxNumPalindrome(string S)
    {
 
        // Index of the string S
        int i = 0;
 
        // Stores the frequency of
        // every character
        int[] freq = new int[26];
 
        // Stores the pair of frequency
        // containing same characters
        int freqPair = 0;
 
        // Number of subsequences
        // having length 3
        int len = S.Length / 3;
 
        // Counts the frequency
        while (i < S.Length)
        {
            freq[S[i] - 'a']++;
            i++;
        }
 
        // Counts the pair of frequency
        for (i = 0; i < 26; i++)
        {
            freqPair += (freq[i] / 2);
        }
 
        // Returns the minimum value
        return Math.Min(freqPair, len);
    }
}
 
// This code is contributed by susmitakundugoaldanga.

<script>
 
// Javascript program to implement
// the above approach
 
// Function to count the maximum number
// oaf palindrome subsequences of length 3
// considering the same index only once
function maxNumPalindrome(S)
{
     
    // Index of the string S
    let i = 0;
 
    // Stores the frequency of
    // every character
    let freq = new Array(26).fill(0);
 
    // Stores the pair of frequency
    // containing same characters
    let freqPair = 0;
 
    // Number of subsequences
    // having length 3
    let len = (S.length / 3);
 
    // Counts the frequency
    while (i < S.length)
    {
        freq[S[i].charCodeAt(0) -
              'a'.charCodeAt(0)]++;
        i++;
    }
 
    // Counts the pair of frequency
    for(i = 0; i < 26; i++)
    {
        freqPair += Math.floor(freq[i] / 2);
    }
 
    // Returns the minimum value
    return Math.min(freqPair, len);
}
 
// Driver Code
let S = "geeksforg";
 
document.write(maxNumPalindrome(S) + "<br>");
 
// This code is contributed by gfgking
 
</script>

2

Complejidad de Tiempo: O(|S| + 26)
Espacio Auxiliar: O(26)