Programa C++ para la subsecuencia más larga de un número que tiene la misma rotación izquierda y derecha

Dada una string numérica S , la tarea es encontrar la longitud máxima de una subsecuencia que tenga su rotación a la izquierda igual a su rotación a la derecha.

Ejemplos:

Entrada: S = “100210601” 
Salida: 4 
Explicación: 
La subsecuencia “0000” cumple la condición necesaria. 
La subsecuencia «1010» genera la string «0101» al girar a la izquierda y la string «0101» al girar a la derecha. Dado que ambas rotaciones son iguales. Por lo tanto, «1010» también cumple la condición. 
Por lo tanto, la longitud máxima de dicha subsecuencia es 4.
Entrada: S = “252525” 
Salida: 6 
Explicación: 
La subsecuencia “252525” genera la string “525252” al girar a la izquierda y la string “525252” al girar a la derecha. Dado que ambas rotaciones son iguales. Por lo tanto, el “252525” cumple la condición requerida.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las subsecuencias posibles de la string dada y, para cada subsecuencia, verificar si su rotación a la izquierda es igual a su rotación a la derecha. 
Complejidad temporal: O(2 ^N * N) 
Espacio auxiliar: O(N)
 

Enfoque eficiente: para optimizar el enfoque anterior, la observación principal es que la subsecuencia debe consistir en un solo carácter o debe tener una longitud uniforme que consista en dos caracteres alternativamente .

Ilustración: 
str = “2424” 
Rotación a la izquierda de la string = “4242” 
Rotación a la derecha de la string = “4242” 
Como podemos ver, dado que el número es de longitud par, tiene dos caracteres que aparecen alternativamente, por lo tanto, la rotación a la izquierda y a la derecha del número dado es igual.
str = “24242” 
Rotación a la izquierda de la string = “42422” 
Rotación a la derecha de la string = “22424” 
Como podemos ver, dado que el número es de longitud impar y tiene dos caracteres que aparecen alternativamente, por lo tanto, la rotación a la izquierda y a la derecha de la número dado no es igual.

Siga los pasos a continuación para resolver el problema:

• Genera todos los números de dos dígitos posibles.
• Para cada número de dos dígitos generado, verifique la ocurrencia alterna de ambos dígitos en la string. Continúe incrementando el conteo para almacenar la longitud de la subsecuencia alterna para la combinación particular.
• Después del recorrido completo de la string, verifique si ambos dígitos son iguales o no. Si se determina que es cierto, actualice el conteo a la respuesta requerida. Si ambos dígitos son iguales, entonces actualice count o count – 1 a la respuesta si el conteo es par o impar respectivamente.
• Repita los pasos anteriores para todas las combinaciones posibles e imprima la cuenta máxima obtenida.

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 find the longest subsequence
// having equal left and right rotation
int findAltSubSeq(string s)
{
    // Length of the string
    int n = s.size(), ans = INT_MIN;
 
    // Iterate for all possible combinations
    // of a two-digit numbers
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            int cur = 0, f = 0;
 
            // Check for alternate occurrence
            // of current combination
            for (int k = 0; k < n; k++) {
 
                if (f == 0 and s[k] - '0' == i) {
                    f = 1;
 
                    // Increment the current value
                    cur++;
                }
                else if (f == 1 and s[k] - '0' == j) {
                    f = 0;
 
                    // Increment the current value
                    cur++;
                }
            }
 
            // If alternating sequence is
            // obtained of odd length
            if (i != j and cur % 2 == 1)
 
                // Reduce to even length
                cur--;
 
            // Update answer to store
            // the maximum
            ans = max(cur, ans);
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    string s = "100210601";
    cout << findAltSubSeq(s);
 
    return 0;
}

4

Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo 
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.
 

Consulte el artículo completo sobre la subsecuencia más larga de un número que tiene la misma rotación a la izquierda y a la derecha para obtener más detalles.