Dada una string S de longitud N , la tarea es eliminar el prefijo más largo de la string que tiene al menos una substring duplicada presente en S.
Nota: la substring duplicada no puede ser el prefijo en sí
Ejemplos:
Entrada: S = «GeeksforGeeks»
Salida: «forGeeks»
Explicación: La substring más larga que tiene un duplicado es «Geeks».
Después de eliminar esto, la string restante se convierte en «forGeeks».Entrada: S = “aaaa”
Salida: “a”
Explicación: Aquí el prefijo más largo que tiene una substring duplicada es “aaaa”.
Entonces, después de eliminar esto, la string restante es «a».
Tenga en cuenta que la string completa no está seleccionada porque entonces la string duplicada es el prefijo en sí.
Planteamiento: El problema se puede resolver a partir de la siguiente idea:
Encuentre todos los caracteres que pueden ser un punto de partida de una substring que es un duplicado del prefijo. Luego, desde estos puntos, encuentre el duplicado del prefijo más largo y elimine ese prefijo.
Siga la ilustración a continuación para una mejor comprensión.
Ilustración:
Por ejemplo, tome S = «aaaa»
Los posibles puntos de partida pueden estar en los índices 1, 2, 3, 4.
Para índice 1: El posible duplicado del prefijo es “aaaa”.
Tiene longitud = 4Para índice 2: El posible duplicado del prefijo es “aaa”.
Tiene longitud = 3Para índice 3: El posible duplicado del prefijo es “aa”.
Tiene longitud = 2Para índice 4: El posible duplicado del prefijo es “a”.
Tiene longitud = 1Así que elimine el prefijo de longitud 4. Por lo tanto, la string se convierte en «a»
Siga el enfoque mencionado a continuación para resolver el problema:
- Use dos punteros: uno al comienzo del prefijo (digamos i , que inicialmente es 0 ) y el otro (digamos j ) para encontrar el punto de inicio de todas las substrings duplicadas posibles.
- Iterar j de 1 a N:
- Si S[j] coincide con S[i], use un puntero (digamos k) e itere tanto i como k para encontrar la longitud de la substring a partir de j , que es un duplicado del prefijo.
- Actualice la longitud máxima.
- Establezca i nuevamente en 0.
- Eliminar el prefijo de longitud máxima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to delete the longest prefix string delPrefix(string S) { if (S.size() == 1) return S; int i = 0, maxi = 0; // Loop to find the // longest duplicate of prefix for (int j = 1; j < S.size(); j++) { int k = j; while (k < S.size() and S[k] == S[i]) { k++; i++; } maxi = max(maxi, i); i = 0; } return S.substr(maxi); } // Driver code int main() { string S = "aaaaa"; string ans = delPrefix(S); // Function call cout << ans; return 0; }
Java
// Java code for the above approach import java.io.*; class GFG { // Function to delete the longest prefix public static String delPrefix(String S) { if (S.length() == 1) return S; int i = 0, maxi = 0; // Loop to find the // longest duplicate of prefix for (int j = 1; j < S.length(); j++) { int k = j; while (k < S.length() && S.charAt(k) == S.charAt(i)) { k++; i++; } maxi = Math.max(maxi, i); i = 0; } return S.substring(maxi); } public static void main(String[] args) { String S = "aaaaa"; String ans = delPrefix(S); // Function call System.out.print(ans); } } // This code is contributed by Rohit Pradhan
Python3
# Python code for the above approach: # Function to delete the longest prefix def delPrefix(S): if (len(S) == 1): return S i = 0 maxi = 0 # Loop to find the # longest duplicate of prefix for j in (1, len(S)+1): k = j while (k < len(S) and S[k] == S[i]): k = k + 1 i = i + 1 maxi = max(maxi, i) i = 0 return S[maxi:] # Driver code S = "aaaaa" ans = delPrefix(S) # Function call print(ans) # This code is contributed by Taranpreet
C#
// C# code for the above approach using System; public class GFG{ // Function to delete the longest prefix public static string delPrefix(string S) { if (S.Length == 1) return S; int i = 0, maxi = 0; // Loop to find the // longest duplicate of prefix for (int j = 1; j < S.Length; j++) { int k = j; while (k < S.Length && S[k] == S[i]) { k++; i++; } maxi = Math.Max(maxi, i); i = 0; } return S.Substring(maxi); } static public void Main (){ string S = "aaaaa"; string ans = delPrefix(S); // Function call Console.Write(ans); } } // This code is contributed by hrithikgarg03188.
Javascript
<script> // JavaScript code for the above approach function delPrefix(S) { if (S.length == 1) return S; let i = 0, maxi = 0; // Loop to find the // longest duplicate of prefix for (let j = 1; j < S.length; j++) { let k = j; while (k < S.length && S[k] == S[i]) { k++; i++; } maxi = Math.max(maxi, i); i = 0; } return S.slice(maxi); } // Driver code let S = "aaaaa"; let ans = delPrefix(S); // Function call document.write(ans) // This code is contributed by Potta Lokesh </script>
a
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mayank007rawa y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA