Dadas dos strings A y B de tamaño N y M respectivamente, la tarea es contar los caracteres de la string A , que cuando se eliminan individualmente igualan ambas strings. Si existen varios de estos caracteres, imprima sus respectivas posiciones. De lo contrario, imprima «-1» .
Ejemplos:
Entrada: A= “abaac”, B =“abac”
Salida: 2
3 4
Explicación:
Son posibles las siguientes eliminaciones que pueden hacer que las strings sean iguales:
- Eliminar A[2] modifica A a «abac», que se vuelve igual a B.
- Eliminar A[3] modifica A a «abac», que se vuelve igual a B.
Por lo tanto, dos posibles eliminaciones satisfacen las condiciones.
Entrada: A = “abs”, B = “bkk”
Salida: -1
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Supongamos que, si eliminando el carácter en el índice i, hace que ambas strings sean iguales, entonces el prefijo de la string, es decir, la substring sobre el rango [0, i-1], debe ser igual y el sufijo de la string, es decir, la substring sobre el rango [i+1 , N-1] también debe ser igual.
- Supongamos que i es el índice que satisface que la substring sobre el rango [0, i-1] es la string de prefijo igual más larga. Y j es el índice que satisface que la substring sobre el rango [j+1, N-1] es la string de sufijo igual más larga
- Entonces, si i>=j entonces solo, existen caracteres que se eliminan, lo que hace que ambas strings sean iguales. Y el recuento total de la eliminación de tales caracteres que individualmente hace que las strings sean iguales es i-j+1.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos X como 0 e Y como N-1 para almacenar el índice final de la string de prefijo igual más larga y el índice inicial de la string de sufijo igual más larga.
- Repita los caracteres de la string B y luego, en cada iteración, verifique si el carácter actual es igual al carácter en el índice X de la string A , luego incremente X en 1 . De lo contrario, rompe.
- Itere sobre los caracteres de la string B al revés y luego, en cada iteración, verifique si el carácter actual es igual al carácter en el índice Y de la string A , luego disminuya Y en 1 . De lo contrario, rompe.
- Ahora bien, si la diferencia entre N y M es igual a 1 e Y es menor que X , entonces:
- Imprime el recuento total de caracteres como X-Y+1.
- Luego imprima los índices del carácter iterando sobre el rango [Y+1, X+1].
- De lo contrario, imprima «-1».
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 count characters
// from string A whose removal
// makes the strings A and B equal
void RemoveOneChar(string A, string B,
int N, int M)
{
// Stores the index of
// the longest prefix
int X = 0;
// Stores the index of
// the longest suffix
int Y = N - 1;
// Traverse the string B
for (int i = 0; i < M; i++) {
if (A[X] != B[i])
break;
X++;
}
// Traverse the string B
for (int i = M - 1; i >= 0; i--) {
if (A[Y] != B[i])
break;
Y--;
}
// If N - M is equal to 1 and Y
// is less than or equal to X
if (N - M == 1 && Y < X) {
// Print the count
// of characters
cout << X - Y + 1 << endl;
// Print the positions
// of the characters
for (int i = Y; i <= X; i++)
cout << i + 1 << " ";
cout << endl;
}
// Otherwise
else
cout << -1 << endl;
}
// Driver Code
int main()
{
string A = "abaac";
string B = "abac";
int N = A.length();
int M = B.length();
RemoveOneChar(A, B, N, M);
}
Java
// Java program for the above approach
class GFG{
// Function to count characters
// from string A whose removal
// makes the strings A and B equal
static void RemoveOneChar(String A, String B,
int N, int M)
{
// Stores the index of
// the longest prefix
int X = 0;
// Stores the index of
// the longest suffix
int Y = N - 1;
// Traverse the string B
for(int i = 0; i < M; i++)
{
if (A.charAt(X) != B.charAt(i))
break;
X++;
}
// Traverse the string B
for(int i = M - 1; i >= 0; i--)
{
if (A.charAt(Y) != B.charAt(i))
break;
Y--;
}
// If N - M is equal to 1 and Y
// is less than or equal to X
if (N - M == 1 && Y < X)
{
// Print the count
// of characters
System.out.println(X - Y + 1);
// Print the positions
// of the characters
for(int i = Y; i <= X; i++)
System.out.print(i + 1 + " ");
System.out.println();
}
// Otherwise
else
System.out.println(-1);
}
// Driver Code
static public void main(String []args)
{
String A = "abaac";
String B = "abac";
int N = A.length();
int M = B.length();
RemoveOneChar(A, B, N, M);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to count characters # from A whose removal # makes the strings A and B equal def RemoveOneChar(A, B, N, M): # Stores the index of # the longest prefix X = 0 # Stores the index of # the longest suffix Y = N - 1 # Traverse the B for i in range(M): if (A[X] != B[i]): break X += 1 # Traverse the B for i in range(M - 1, -1, -1): if (A[Y] != B[i]): break Y -= 1 # If N - M is equal to 1 and Y # is less than or equal to X if (N - M == 1 and Y < X): # Print count # of characters print(X - Y + 1) # Print positions # of the characters for i in range(Y, X + 1): print(i + 1, end = " ") print() # Otherwise else: print(-1) # Driver Code if __name__ == '__main__': A = "abaac" B = "abac" N = len(A) M = len(B) RemoveOneChar(A, B, N, M) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
public class GFG{
// Function to count characters
// from string A whose removal
// makes the strings A and B equal
static void RemoveOneChar(string A, string B,
int N, int M)
{
// Stores the index of
// the longest prefix
int X = 0;
// Stores the index of
// the longest suffix
int Y = N - 1;
// Traverse the string B
for (int i = 0; i < M; i++) {
if (A[X] != B[i])
break;
X++;
}
// Traverse the string B
for (int i = M - 1; i >= 0; i--) {
if (A[Y] != B[i])
break;
Y--;
}
// If N - M is equal to 1 and Y
// is less than or equal to X
if (N - M == 1 && Y < X) {
// Print the count
// of characters
Console.WriteLine(X - Y + 1);
// Print the positions
// of the characters
for (int i = Y; i <= X; i++)
Console.Write(i + 1 + " ");
Console.WriteLine();
}
// Otherwise
else
Console.WriteLine(-1) ;
}
// Driver Code
static public void Main (){
string A = "abaac";
string B = "abac";
int N = A.Length;
int M = B.Length;
RemoveOneChar(A, B, N, M);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
// Function to count characters
// from string A whose removal
// makes the strings A and B equal
function RemoveOneChar(A, B, N, M)
{
// Stores the index of
// the longest prefix
var X = 0;
// Stores the index of
// the longest suffix
var Y = N - 1;
var i;
// Traverse the string B
for (i = 0; i < M; i++) {
if (A[X] != B[i])
break;
X++;
}
// Traverse the string B
for (i = M - 1; i >= 0; i--) {
if (A[Y] != B[i])
break;
Y--;
}
// If N - M is equal to 1 and Y
// is less than or equal to X
if (N - M == 1 && Y < X) {
// Print the count
// of characters
document.write(X - Y + 1 + "<br>");
// Print the positions
// of the characters
for (i = Y; i <= X; i++)
document.write(i + 1 +" ");
document.write("\n");
}
// Otherwise
else
document.write(-1);
}
// Driver Code
var A = "abaac";
var B = "abac";
var N = A.length;
var M = B.length;
RemoveOneChar(A, B, N, M);
</script>
Producción:
2 3 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por samarpitsmarty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA