Dada una string S de longitud N que consta solo de los caracteres ‘a’ , ‘b’ y ‘c’ , la tarea es minimizar la longitud de la string dada realizando las siguientes operaciones solo una vez:
- Divida la string en dos substrings no vacías y luego agregue la substring izquierda al final de la substring derecha.
- Al agregar, si el sufijo de la substring derecha y el prefijo de la substring izquierda contienen el mismo carácter, elimine esos caracteres del sufijo y prefijo de las substrings derecha e izquierda respectivamente. Repita este paso hasta que no haya substrings que no se puedan quitar.
Ejemplos:
Entrada: S = “aabcccabba”
Salida : 4
Explicación:
Divide la string S dada en dos partes como “aabcc” y “cabba” . A continuación se muestran las operaciones realizadas en las dos substrings anteriores:
- Elimina los prefijos y sufijos de los mismos caracteres, es decir, ‘a’ . La string se convierte en “bcc” y “cabb” .
- Elimina los sufijos y prefijos de los mismos caracteres, es decir, ‘b’ . La string se convierte en “cc” y “ca” .
Ahora, después de concatenar las substrings derecha e izquierda, la string obtenida es “cacc” , que es la de menor longitud, es decir, 4.
Entrada: S = “aacbcca”
Salida: 1
Enfoque: el problema dado se puede resolver usando Two Pointers al encontrar caracteres similares presentes en el sufijo de la string y el prefijo de la string .
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos i como 0 y j como (N – 1) .
- Iterar un bucle hasta que i < j y los caracteres S[i] y S[j] sean iguales y realizar los siguientes pasos:
- Inicialice una variable, digamos d con S[i] , y mueva el puntero i hacia la derecha mientras i es como máximo j y d = S[i] .
- Desplace el puntero j hacia la izquierda hasta que i sea como máximo j y d = S[j] .
- Después de completar los pasos anteriores, el valor de (j – i + 1) es la longitud mínima posible de la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the minimum length
// of the string after removing the same
// characters from the end and front of the
// two strings after dividing into 2 substrings
int minLength(string s)
{
// Initialize two pointers
int i = 0, j = s.length() - 1;
// Traverse the string S
for(; i < j && s[i] == s[j];)
{
// Current char on left pointer
char d = s[i];
// Shift i towards right
while (i <= j && s[i] == d)
i++;
// Shift j towards left
while (i <= j && s[j] == d)
j--;
}
// Return the minimum possible
// length of string
return j - i + 1;
}
// Driver Code
int main()
{
string S = "aacbcca";
cout << minLength(S);
}
// This code is contributed by bgangwar59
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG {
// Function to find the minimum length
// of the string after removing the same
// characters from the end and front of the
// two strings after dividing into 2 substrings
static int minLength(String s)
{
// Initialize two pointers
int i = 0, j = s.length() - 1;
// Traverse the string S
for (; i < j
&& s.charAt(i) == s.charAt(j);) {
// Current char on left pointer
char d = s.charAt(i);
// Shift i towards right
while (i <= j
&& s.charAt(i) == d)
i++;
// Shift j towards left
while (i <= j
&& s.charAt(j) == d)
j--;
}
// Return the minimum possible
// length of string
return j - i + 1;
}
// Driver Code
public static void main(String[] args)
{
String S = "aacbcca";
System.out.println(minLength(S));
}
}
Python3
# Python3 program for the above approach # Function to find the minimum length # of the string after removing the same # characters from the end and front of the # two strings after dividing into 2 substrings def minLength(s): # Initialize two pointers i = 0; j = len(s) - 1 # Traverse the string S while (i < j and s[i] == s[j]): # Current char on left pointer d = s[i] # Shift i towards right while (i <= j and s[i] == d): i += 1 # Shift j towards left while (i <= j and s[j] == d): j -= 1 # Return the minimum possible # length of string return j - i + 1 # Driver Code if __name__ == "__main__" : S = "aacbcca" print(minLength(S)) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum length
// of the string after removing the same
// characters from the end and front of the
// two strings after dividing into 2 substrings
static int minLength(string s)
{
// Initialize two pointers
int i = 0, j = s.Length - 1;
// Traverse the string S
for(; i < j && s[i] == s[j];)
{
// Current char on left pointer
char d = s[i];
// Shift i towards right
while (i <= j && s[i] == d)
i++;
// Shift j towards left
while (i <= j && s[j] == d)
j--;
}
// Return the minimum possible
// length of string
return j - i + 1;
}
// Driver Code
public static void Main(string[] args)
{
string S = "aacbcca";
Console.WriteLine(minLength(S));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum length
// of the string after removing the same
// characters from the end and front of the
// two strings after dividing into 2 substrings
function minLength(s)
{
// Initialize two pointers
i = 0; j = s.length - 1
// Traverse the string S
while (i < j && s[i] == s[j]){
// Current char on left pointer
d = s[i]
// Shift i towards right
while (i <= j && s[i] == d)
i += 1
// Shift j towards left
while (i <= j && s[j] == d)
j -= 1
// Return the minimum possible
// length of string
}
return j - i + 1
}
// Driver Code
S = "aacbcca"
document.write(minLength(S))
// This code is contributed by AnkThon
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)