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 y aparecen dos caracteres 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++
// 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;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the longest subsequence
// having equal left and right rotation
static int findAltSubSeq(String s)
{
// Length of the String
int n = s.length(), ans = Integer.MIN_VALUE;
// 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 && s.charAt(k) - '0' == i)
{
f = 1;
// Increment the current value
cur++;
}
else if (f == 1 &&
s.charAt(k) - '0' == j)
{
f = 0;
// Increment the current value
cur++;
}
}
// If alternating sequence is
// obtained of odd length
if (i != j && cur % 2 == 1)
// Reduce to even length
cur--;
// Update answer to store
// the maximum
ans = Math.max(cur, ans);
}
}
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
String s = "100210601";
System.out.print(findAltSubSeq(s));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to implement
# the above approach
import sys
# Function to find the longest subsequence
# having equal left and right rotation
def findAltSubSeq(s):
# Length of the string
n = len(s)
ans = -sys.maxsize - 1
# Iterate for all possible combinations
# of a two-digit numbers
for i in range(10):
for j in range(10):
cur, f = 0, 0
# Check for alternate occurrence
# of current combination
for k in range(n):
if (f == 0 and ord(s[k]) -
ord('0') == i):
f = 1
# Increment the current value
cur += 1
elif (f == 1 and ord(s[k]) -
ord('0') == j):
f = 0
# Increment the current value
cur += 1
# If alternating sequence is
# obtained of odd length
if i != j and cur % 2 == 1:
# Reduce to even length
cur -= 1
# Update answer to store
# the maximum
ans = max(cur, ans)
# Return the answer
return ans
# Driver code
s = "100210601"
print(findAltSubSeq(s))
# This code is contributed by Stuti Pathak
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to find the longest subsequence
// having equal left and right rotation
static int findAltSubSeq(String s)
{
// Length of the String
int n = s.Length, ans = int.MinValue;
// 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 && s[k] - '0' == i)
{
f = 1;
// Increment the current value
cur++;
}
else if (f == 1 &&
s[k] - '0' == j)
{
f = 0;
// Increment the current value
cur++;
}
}
// If alternating sequence is
// obtained of odd length
if (i != j && cur % 2 == 1)
// Reduce to even length
cur--;
// Update answer to store
// the maximum
ans = Math.Max(cur, ans);
}
}
// Return the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String s = "100210601";
Console.Write(findAltSubSeq(s));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to find the longest subsequence
// having equal left and right rotation
function findAltSubSeq(s)
{
// Length of the string
var n = s.length, ans = -1000000000;
// Iterate for all possible combinations
// of a two-digit numbers
for (var i = 0; i < 10; i++) {
for (var j = 0; j < 10; j++) {
var cur = 0, f = 0;
// Check for alternate occurrence
// of current combination
for (var k = 0; k < n; k++) {
if (f == 0 && s[k] - '0' == i) {
f = 1;
// Increment the current value
cur++;
}
else if (f == 1 && s[k] - '0' == j) {
f = 0;
// Increment the current value
cur++;
}
}
// If alternating sequence is
// obtained of odd length
if (i != j && cur % 2 == 1)
// Reduce to even length
cur--;
// Update answer to store
// the maximum
ans = Math.max(cur, ans);
}
}
// Return the answer
return ans;
}
// Driver Code
var s = "100210601";
document.write( findAltSubSeq(s));
</script>
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.
Publicación traducida automáticamente
Artículo escrito por rohansadhukhan9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA