Substring palindrómica más larga | conjunto 2

Dada una string, encuentra la substring más larga que es un palíndromo. 

Ejemplos: 

Input: Given string :"forgeeksskeegfor", 
Output: "geeksskeeg".

Input: Given string :"Geeks", 
Output: "ee". 

Error común: enfoque incorrecto:   

Algunas personas se verán tentadas a encontrar una solución rápida de complejidad de tiempo O(n) , que desafortunadamente es defectuosa (sin embargo, se puede corregir fácilmente):

 (i) Invertir S y almacenarlo en S’. 
 (ii) Encuentre la substring común más larga entre S y S’, que también debe ser la substring palindrómica más larga.

Esto pareció funcionar, veamos algunos ejemplos a continuación.

Por ejemplo, S = “caba” luego S’ = “abac”.

La substring común más larga entre S y S’ es «aba», que es la respuesta.

Probemos con otro ejemplo: S = “abacdfgdcaba” luego S’ = “abacdgfdcaba”.

La substring común más larga entre S y S’ es «abacd». Claramente, este no es un palíndromo válido.

Enfoque correcto:

Podríamos ver que el método de la substring común más larga falla cuando existe una copia invertida de una substring no palindrómica en alguna otra parte de S. Para rectificar esto, cada vez que encontramos un candidato a la substring común más larga, verificamos si los índices de la substring son lo mismo que los índices originales de la substring invertida. Si es así, intentamos actualizar el palíndromo más largo encontrado hasta ahora; si no, nos saltamos esto y buscamos el siguiente candidato. Esto nos da una solución de programación dinámica O (n ^ 2) que usa el espacio O (n ^ 2) (que podría mejorarse para usar el espacio O (n)).

Enfoque de programación dinámica: la solución de programación dinámica ya se discutió aquí en la publicación anterior . La complejidad temporal de la solución basada en Programación Dinámica es O(n^2) y requiere O(n^2) espacio adicional. Podemos encontrar la substring de palíndromo más larga (LPS) en (n ^ 2) tiempo con O (1) espacio adicional. 

El siguiente algoritmo es muy simple y fácil de entender. La idea es fijar un centro y expandirse en ambas direcciones para palíndromos más largos y realizar un seguimiento del palíndromo más largo visto hasta ahora.

ALGO:

1. Mantenga una variable ‘ maxLength = 1 ‘ (para almacenar la longitud de LPS) y ‘start =0’ (para almacenar el índice inicial de LPS).
2. La idea es muy simple, recorreremos toda la string con i=0 a i<(longitud de la string).
   1. mientras se desplaza, inicialice el puntero ‘bajo ‘ y ‘alto ‘ de modo que bajo= i-1 y alto= i+1.
   2. sigue incrementando ‘high’ hasta str[high]==str[i] .
   3. de manera similar, siga disminuyendo ‘low’ hasta str[low]==str[i] .
   4. finalmente seguiremos incrementando ‘high’ y decrementando ‘low’ hasta str[low]==str[high] .
   5. calcule length=high-low-1, si length > maxLength entonces maxLength = length y start = low+1 .
3. Imprima el LPS y devuelva maxLength.
    

// A O(n^2) time and O(1) space program to
// find the longest palindromic substring
// easy to understand as compared to previous version.
#include <bits/stdc++.h>
using namespace std;
 
// A utility function to print
// a substring str[low..high]
// This function prints the
// longest palindrome substring (LPS)
// of str[]. It also returns the
// length of the longest palindrome
int longestPalSubstr(string str)
{
    int n = str.size(); // calculating size of string
    if (n < 2)
        return n; // if string is empty then size will be 0.
                  // if n==1 then, answer will be 1(single
                  // character will always palindrome)
 
    int maxLength = 1, start = 0;
    int low, high;
    for (int i = 0; i < n; i++) {
        low = i - 1;
        high = i + 1;
        while (high < n
               && str[high] == str[i]) // increment 'high'
            high++;
 
        while (low >= 0
               && str[low] == str[i]) // decrement 'low'
            low--;
 
        while (low >= 0 && high < n
               && str[low] == str[high]) {
            low--;
            high++;
        }
 
        int length = high - low - 1;
        if (maxLength < length) {
            maxLength = length;
            start = low + 1;
        }
    }
 
    cout << "Longest palindrome substring is: ";
    cout << str.substr(start, maxLength);
    return maxLength;
}
 
// Driver program to test above functions
int main()
{
    string str = "forgeeksskeegfor";
    cout << "\nLength is: " << longestPalSubstr(str)
         << endl;
    return 0;
}

// A O(n^2) time and O(1) space
// program to find the longest
// palindromic substring
#include <stdio.h>
#include <string.h>
 
// A utility function to print
// a substring str[low..high]
void printSubStr(char* str, int low, int high)
{
    for (int i = low; i <= high; ++i)
        printf("%c", str[i]);
}
 
// This function prints the longest
// palindrome substring (LPS)
// of str[]. It also returns the
// length of the longest palindrome
int longestPalSubstr(char* str)
{
    int n = strlen(str); // calculating size of string
    if (n < 2)
        return n; // if string is empty then size will be 0.
                  // if n==1 then, answer will be 1(single
                  // character will always palindrome)
 
    int maxLength = 1, start = 0;
    int low, high;
    for (int i = 0; i < n; i++) {
        low = i - 1;
        high = i + 1;
        while (high < n
               && str[high] == str[i]) // increment 'high'
            high++;
 
        while (low >= 0
               && str[low] == str[i]) // decrement 'low'
            low--;
 
        while (low >= 0 && high < n
               && str[low] == str[high]) {
            low--; // decrement low
            high++; // increment high
        }
 
        int length = high - low - 1;
        if (maxLength < length) {
            maxLength = length;
            start = low + 1;
        }
    }
    printf("Longest palindrome substring is: ");
    printSubStr(str, start, start + maxLength - 1);
    return maxLength;
}
 
// Driver program to test above functions
int main()
{
    char str[] = "forgeeksskeegfor";
    printf("\nLength is: %d", longestPalSubstr(str));
    return 0;
}

// Java implementation of O(n^2)
// time and O(1) space method
// to find the longest palindromic substring
public class LongestPalinSubstring {
   
    // This function prints the
    // longest palindrome substring
    // (LPS) of str[]. It also
    // returns the length of the
    // longest palindrome
    static int longestPalSubstr(String str)
    {
        int n = str.length(); // calculcharAting size of string
        if (n < 2)
            return n; // if string is empty then size will be 0.
                  // if n==1 then, answer will be 1(single
                  // character will always palindrome)
 
        int maxLength = 1,start=0;
        int low, high;
        for (int i = 0; i < n; i++) {
            low = i - 1;
            high = i + 1;
            while ( high < n && str.charAt(high) == str.charAt(i)) //increment 'high'                                  
                high++;
       
            while ( low >= 0 && str.charAt(low) == str.charAt(i)) // decrement 'low'                   
                low--;
       
            while (low >= 0 && high < n && str.charAt(low) == str.charAt(high) ){
                  low--;
                high++;
        }
 
        int length = high - low - 1;
        if (maxLength < length){
            maxLength = length;
            start=low+1;
        }
    }   
    System.out.print("Longest palindrome substring is: ");
    System.out.println(str.substring(start, start + maxLength ));
    return maxLength;
       
 }
 
    // Driver program to test above function
    public static void main(String[] args)
    {
 
        String str = "forgeeksskeegfor";
        System.out.println("Length is: "
                           + longestPalSubstr(str));
    }
}

# A O(n ^ 2) time and O(1) space program to find the
# longest palindromic substring
 
# This function prints the longest palindrome substring (LPS)
# of str[]. It also returns the length of the longest palindrome
 
 
def longestPalSubstr(string):
    n = len(string) # calculating size of string
    if (n < 2):
        return n # if string is empty then size will be 0.
                  # if n==1 then, answer will be 1(single
                  # character will always palindrome)
    start=0
    maxLength = 1
    for i in range(n):
        low = i - 1
        high = i + 1
        while (high < n and string[high] == string[i] ):                              
            high=high+1
       
        while (low >= 0 and string[low] == string[i] ):                
            low=low-1
       
        while (low >= 0 and high < n and string[low] == string[high] ):
          low=low-1
          high=high+1
         
     
        length = high - low - 1
        if (maxLength < length):
            maxLength = length
            start=low+1
             
    print ("Longest palindrome substring is:",end=" ")
    print (string[start:start + maxLength])
     
    return maxLength
     
# Driver program to test above functions
string = ("forgeeksskeegfor")
print("Length is: " + str(longestPalSubstr(string)))

// C# implementation of O(n^2) time
// and O(1) space method to find the
// longest palindromic substring
using System;
 
class GFG {
 
    // This function prints the longest
    // palindrome substring (LPS) of str[].
    // It also returns the length of the
    // longest palindrome
    public static int longestPalSubstr(string str)
    {
        int n = str.Length; // calculcharAting size of string
        if (n < 2)
            return n; // if string is empty then size will be 0.
                  // if n==1 then, answer will be 1(single
                  // character will always palindrome)
 
        int maxLength = 1,start=0;
        int low, high;
        for (int i = 0; i < n; i++) {
            low = i - 1;
            high = i + 1;
            while ( high < n && str[high] == str[i] ) //increment 'high'                                  
                high++;
       
            while ( low >= 0 && str[low] == str[i]) // decrement 'low'                   
                low--;
       
            while (low >= 0 && high < n && str[low] == str[high] ){
                  low--;
                high++;
        }
 
        int length = high - low - 1;
        if (maxLength < length){
            maxLength = length;
            start=low+1;
        }
    }   
    Console.Write("Longest palindrome substring is: ");
    Console.WriteLine(str.Substring(start, maxLength));
    return maxLength;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        string str = "forgeeksskeegfor";
        Console.WriteLine("Length is: "
                          + longestPalSubstr(str));
    }
}

<script>
 
// A O(n^2) time and O(1) space program to
// find the longest palindromic substring
// easy to understand as compared to previous version.
 
// A utility function to print
// a substring str[low..high]
// This function prints the
// longest palindrome substring (LPS)
// of str[]. It also returns the
// length of the longest palindrome
function longestPalSubstr(str)
{
    let n = str.length; // calculating size of string
    if (n < 2)
        return n; // if string is empty then size will be 0.
                // if n==1 then, answer will be 1(single
                // character will always palindrome)
 
    let maxLength = 1,start=0;
    let low, high;
    for (let i = 0; i < n; i++) {
        low = i - 1;
        high = i + 1;
        while ( high < n && str[high] == str[i]) //increment 'high'                               
            high++;
     
        while ( low >= 0 && str[low] == str[i]) // decrement 'low'               
            low--;
     
        while (low >= 0 && high < n && str[low] == str[high]){
            low--;
            high++;
        }
 
        let length = high - low - 1;
        if (maxLength < length) {
            maxLength = length;
            start=low+1;
        }
    }
     
    document.write("Longest palindrome substring is: ");
    document.write(str.substring(start,maxLength+start));
    return maxLength;
}
 
// Driver program to test above functions
 
let str = "forgeeksskeegfor";
document.write("</br>","Length is: " + longestPalSubstr(str),"</br>");
 
 
</script>

Longest palindrome substring is: geeksskeeg
Length is: 10

Análisis de Complejidad:  

• Complejidad de tiempo: O(n^2), donde n es la longitud de la string de entrada. 
  Bucle externo que atraviesa toda la string y Bucle interno que se usa para expandirse desde i .
• Espacio Auxiliar: O(1). 
  No se necesita espacio adicional.

El enfoque anterior es una forma más limpia.

La implementación de la función para imprimir el LPS y devolver el maxLength se muestra a continuación:

// A O(n^2) time and O(1) space program to
// find the longest palindromic substring
// easy to understand as compared to previous version.
 
#include <bits/stdc++.h>
using namespace std;
 
int maxLength; // variables to store and
string res; // update  maxLength and res
 
// A utility function to get the longest palindrome
// starting and expanding out from given center indices
void cSubUtil(string& s, int l, int r)
{
    // check if the indices lie in the range of string
    // and also if it is palindrome
    while (l >= 0 && r < s.length() && s[l] == s[r]) {
        // expand the boundary
        l--;
        r++;
    }
    // if it's length is greater than maxLength update
    // maxLength and res
    if (r - l - 1 >= maxLength) {
        res = s.substr(l + 1, r - l - 1);
        maxLength = r - l - 1;
    }
    return;
}
// A function which takes a string prints the LPS and
// returns the length of LPS
int longestPalSubstr(string str)
{
    res = "";
    maxLength = 1;
    // for every index in the string check palindromes
    // starting from that index
    for (int i = 0; i < str.length(); i++) {
        // check for odd length palindromes
        cSubUtil(str, i, i);
        // check for even length palindromes
        cSubUtil(str, i, i + 1);
    }
 
    cout << "Longest palindrome substring is: ";
    cout << res << "\n";
 
    return maxLength;
}
 
// Driver program to test above functions
int main()
{
    string str = "forgeeksskeegfor";
    cout << "\nLength is: " << longestPalSubstr(str)
         << endl;
    return 0;
}

// Java implementation of O(n^2)
// time and O(1) space method
// to find the longest palindromic substring
 
public class LongestPalinSubstring {
 
    static int maxLength; // variables to store and
    static String res; // update  maxLength and res
 
    // A utility function to get the longest palindrome
    // starting and expanding out from given center indices
    static void cSubUtil(String s, int l, int r)
    {
        // check if the indices lie in the range of string
        // and also if it is palindrome
        while (l >= 0 && r < s.length()
               && s.charAt(l) == s.charAt(r)) {
            // expand the boundary
            l--;
            r++;
        }
        // if it's length is greater than maxLength update
        // maxLength and res
        if (r - l - 1 >= maxLength) {
            res = s.substring(l + 1, r);
            maxLength = r - l - 1;
        }
        return;
    }
    // A function which takes a string prints the LPS and
    // returns the length of LPS
    static int longestPalSubstr(String str)
    {
        res = "";
        maxLength = 1;
        // for every index in the string check palindromes
        // starting from that index
        for (int i = 0; i < str.length(); i++) {
            // check for odd length palindromes
            cSubUtil(str, i, i);
            // check for even length palindromes
            cSubUtil(str, i, i + 1);
        }
        System.out.print(
            "Longest palindrome substring is: ");
        System.out.println(res);
        return maxLength;
    }
 
    // Driver program to test above function
    public static void main(String[] args)
    {
 
        String str = "forgeeksskeegfor";
        System.out.println("Length is: "
                           + longestPalSubstr(str));
    }
}

// C# implementation of O(n^2) time
// and O(1) space method to find the
// longest palindromic substring
using System;
 
class GFG {
 
    static int maxLength; // variables to store and
    static string res; // update  maxLength and res
 
    // A utility function to get the longest palindrome
    // starting and expanding out from given center indices
    public static void cSubUtil(string s, int l, int r)
    {
        // check if the indices lie in the range of string
        // and also if it is palindrome
        while (l >= 0 && r < s.Length && s[l] == s[r]) {
            // expand the boundary
            l--;
            r++;
        }
        // if it's length is greater than maxLength update
        // maxLength and res
        if (r - l - 1 >= maxLength) {
            res = s.Substring(l + 1, r - l - 1);
            maxLength = r - l - 1;
        }
        return;
    }
    // A function which takes a string prints the LPS and
    // returns the length of LPS
    public static int longestPalSubstr(string str)
    {
        res = "";
        maxLength = 1;
        // for every index in the string check palindromes
        // starting from that index
        for (int i = 0; i < str.Length; i++) {
            // check for odd length palindromes
            cSubUtil(str, i, i);
            // check for even length palindromes
            cSubUtil(str, i, i + 1);
        }
 
        Console.Write("Longest palindrome substring is: ");
        Console.WriteLine(res);
        return maxLength;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        string str = "forgeeksskeegfor";
        Console.WriteLine("Length is: "
                          + longestPalSubstr(str));
    }
}

Longest palindrome substring is: geeksskeeg

Length is: 10

Escriba comentarios si encuentra algo incorrecto o si tiene más información sobre el tema tratado anteriormente.