Longitud de la substring de palíndromo más larga

Dada una string S de longitud N , la tarea es encontrar la longitud de la substring palindrómica más larga de una string dada.

Ejemplos: 

Entrada: S = «abcbab»
Salida: 5
Explicación: 
la string «abcba» es la substring más larga que es un palíndromo que tiene una longitud de 5.

Entrada: S = «abcdaa»
Salida: 2
Explicación: 
la string «aa» es la substring más larga que es un palíndromo que tiene una longitud de 2. 

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las substrings posibles de la string dada e imprimir la longitud de la substring más larga , que es un palíndromo .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to obtain the length of
// the longest palindromic substring
int longestPalSubstr(string str)
{
    // Length of given string
    int n = str.size();
 
    // Stores the maximum length
    int maxLength = 1, start = 0;
 
    // Iterate over the string
    for (int i = 0;
         i < str.length(); i++) {
 
        // Iterate over the string
        for (int j = i;
             j < str.length(); j++) {
            int flag = 1;
 
            // Check for palindrome
            for (int k = 0;
                 k < (j - i + 1) / 2; k++)
                if (str[i + k]
                    != str[j - k])
                    flag = 0;
 
            // If string [i, j - i + 1]
            // is palindromic
            if (flag
                && (j - i + 1) > maxLength) {
                start = i;
                maxLength = j - i + 1;
            }
        }
    }
 
    // Return length of LPS
    return maxLength;
}
 
// Driver Code
int main()
{
    // Given string
    string str = "forgeeksskeegfor";
 
    // Function Call
    cout << longestPalSubstr(str);
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
  
// Function to obtain the length of
// the longest palindromic substring
static int longestPalSubstr(String str)
{
     
    // Length of given string
    int n = str.length();
  
    // Stores the maximum length
    int maxLength = 1, start = 0;
  
    // Iterate over the string
    for(int i = 0; i < str.length(); i++)
    {
         
        // Iterate over the string
        for(int j = i; j < str.length(); j++)
        {
            int flag = 1;
  
            // Check for palindrome
            for(int k = 0;
                    k < (j - i + 1) / 2; k++)
                if (str.charAt(i + k) !=
                    str.charAt(j - k))
                    flag = 0;
  
            // If string [i, j - i + 1]
            // is palindromic
            if (flag != 0 &&
               (j - i + 1) > maxLength)
            {
                start = i;
                maxLength = j - i + 1;
            }
        }
    }
  
    // Return length of LPS
    return maxLength;
}
  
// Driver Code
public static void main (String[] args)
{
     
    // Given string
    String str = "forgeeksskeegfor";
  
    // Function call
    System.out.print(longestPalSubstr(str));
}
}
 
// This code is contributed by code_hunt

# Python3 program for the above approach
 
# Function to obtain the length of
# the longest palindromic substring
def longestPalSubstr(str):
     
    # Length of given string
    n = len(str)
  
    # Stores the maximum length
    maxLength = 1
    start = 0
  
    # Iterate over the string
    for i in range(len(str)):
  
        # Iterate over the string
        for j in range(i, len(str), 1):
            flag = 1
  
            # Check for palindrome
            for k in range((j - i + 1) // 2):
                if (str[i + k] != str[j - k]):
                    flag = 0
  
            # If string [i, j - i + 1]
            # is palindromic
            if (flag != 0 and
               (j - i + 1) > maxLength):
                start = i
                maxLength = j - i + 1
             
    # Return length of LPS
    return maxLength
 
# Driver Code
 
# Given string
str = "forgeeksskeegfor"
  
# Function call
print(longestPalSubstr(str))
 
# This code is contributed by code_hunt

// C# program for the above approach 
using System;
 
class GFG{
  
// Function to obtain the length of
// the longest palindromic substring
static int longestPalSubstr(string str)
{
     
    // Length of given string
    int n = str.Length;
  
    // Stores the maximum length
    int maxLength = 1, start = 0;
  
    // Iterate over the string
    for(int i = 0; i < str.Length; i++)
    {
         
        // Iterate over the string
        for(int j = i; j < str.Length; j++)
        {
            int flag = 1;
  
            // Check for palindrome
            for(int k = 0;
                    k < (j - i + 1) / 2; k++)
                if (str[i + k] != str[j - k])
                    flag = 0;
  
            // If string [i, j - i + 1]
            // is palindromic
            if (flag != 0 &&
               (j - i + 1) > maxLength)
            {
                start = i;
                maxLength = j - i + 1;
            }
        }
    }
  
    // Return length of LPS
    return maxLength;
}
  
// Driver Code
public static void Main ()
{
     
    // Given string
    string str = "forgeeksskeegfor";
  
    // Function call
    Console.Write(longestPalSubstr(str));
}
}
 
// This code is contributed by code_hunt

<script>
 
// JavaScript program for the above approach
 
// Function to obtain the length of
// the longest palindromic substring
function longestPalSubstr(str)
{
    // Length of given string
    var n = str.length;
 
    // Stores the maximum length
    var maxLength = 1, start = 0;
 
    // Iterate over the string
    for (var i = 0;
         i < str.length; i++) {
 
        // Iterate over the string
        for (var j = i;
             j < str.length; j++) {
            var flag = 1;
 
            // Check for palindrome
            for (var k = 0;
                 k < (j - i + 1) / 2; k++)
                if (str[i + k]
                    != str[j - k])
                    flag = 0;
 
            // If string [i, j - i + 1]
            // is palindromic
            if (flag
                && (j - i + 1) > maxLength) {
                start = i;
                maxLength = j - i + 1;
            }
        }
    }
 
    // Return length of LPS
    return maxLength;
}
 
// Driver Code
 
// Given string
var str = "forgeeksskeegfor";
 
// Function Call
document.write( longestPalSubstr(str));
 
 
</script>

10

Complejidad de tiempo: O(N ³ ), donde N es la longitud de la string dada. 
Espacio Auxiliar: O(N) 

Enfoque de programación dinámica : el enfoque anterior se puede optimizar almacenando los resultados de los subproblemas superpuestos . La idea es similar a este post . A continuación se muestran los pasos: 

1. Mantenga una tabla booleana [N][N] que se llene de abajo hacia arriba.
2. El valor de table[i][j] es verdadero si la substring es un palíndromo; de lo contrario, es falso.
3. Para calcular table[i][j] , verifique el valor de table[i + 1][j – 1] , si el valor es verdadero y str[i] es igual a str[j] , luego actualice table[i] [j] cierto.
4. De lo contrario, el valor de la tabla[i][j] se actualiza como falso.

A continuación se muestra la ilustración de la string «geeks» : 

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of
// the longest palindromic substring
int longestPalSubstr(string str)
{
    // Length of string str
    int n = str.size();
 
    // Stores the dp states
    bool table[n][n];
 
    // Initialise table[][] as false
    memset(table, 0, sizeof(table));
 
    // All substrings of length 1
    // are palindromes
    int maxLength = 1;
 
    for (int i = 0; i < n; ++i)
        table[i][i] = true;
 
    // Check for sub-string of length 2
    int start = 0;
 
    for (int i = 0; i < n - 1; ++i) {
 
        // If adjacent character are same
        if (str[i] == str[i + 1]) {
 
            // Update table[i][i + 1]
            table[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
 
    // Check for lengths greater than 2
    // k is length of substring
    for (int k = 3; k <= n; ++k) {
 
        // Fix the starting index
        for (int i = 0; i < n - k + 1; ++i) {
 
            // Ending index of substring
            // of length k
            int j = i + k - 1;
 
            // Check for palindromic
            // substring str[i, j]
            if (table[i + 1][j - 1]
                && str[i] == str[j]) {
 
                // Mark true
                table[i][j] = true;
 
                // Update the maximum length
                if (k > maxLength) {
                    start = i;
                    maxLength = k;
                }
            }
        }
    }
 
    // Return length of LPS
    return maxLength;
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "forgeeksskeegfor";
 
    // Function Call
    cout << longestPalSubstr(str);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the length of
// the longest palindromic subString
static int longestPalSubstr(String str)
{
     
    // Length of String str
    int n = str.length();
 
    // Stores the dp states
    boolean [][]table = new boolean[n][n];
 
    // All subStrings of length 1
    // are palindromes
    int maxLength = 1;
 
    for(int i = 0; i < n; ++i)
        table[i][i] = true;
 
    // Check for sub-String of length 2
    int start = 0;
 
    for(int i = 0; i < n - 1; ++i)
    {
         
        // If adjacent character are same
        if (str.charAt(i) == str.charAt(i + 1))
        {
             
            // Update table[i][i + 1]
            table[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
 
    // Check for lengths greater than 2
    // k is length of subString
    for(int k = 3; k <= n; ++k)
    {
         
        // Fix the starting index
        for(int i = 0; i < n - k + 1; ++i)
        {
             
            // Ending index of subString
            // of length k
            int j = i + k - 1;
 
            // Check for palindromic
            // subString str[i, j]
            if (table[i + 1][j - 1] &&
                str.charAt(i) == str.charAt(j))
            {
                 
                // Mark true
                table[i][j] = true;
 
                // Update the maximum length
                if (k > maxLength)
                {
                    start = i;
                    maxLength = k;
                }
            }
        }
    }
     
    // Return length of LPS
    return maxLength;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given String str
    String str = "forgeeksskeegfor";
 
    // Function Call
    System.out.print(longestPalSubstr(str));
}
}
 
// This code is contributed by Amit Katiyar

// C# program for
// the above approach
using System;
class GFG{
 
// Function to find the length of
// the longest palindromic subString
static int longestPalSubstr(String str)
{
  // Length of String str
  int n = str.Length;
 
  // Stores the dp states
  bool [,]table = new bool[n, n];
 
  // All subStrings of length 1
  // are palindromes
  int maxLength = 1;
 
  for(int i = 0; i < n; ++i)
    table[i, i] = true;
 
  // Check for sub-String
  // of length 2
  int start = 0;
 
  for(int i = 0; i < n - 1; ++i)
  {
    // If adjacent character are same
    if (str[i] == str[i + 1])
    {
      // Update table[i,i + 1]
      table[i, i + 1] = true;
      start = i;
      maxLength = 2;
    }
  }
 
  // Check for lengths greater than 2
  // k is length of subString
  for(int k = 3; k <= n; ++k)
  {
    // Fix the starting index
    for(int i = 0; i < n - k + 1; ++i)
    {
      // Ending index of subString
      // of length k
      int j = i + k - 1;
 
      // Check for palindromic
      // subString str[i, j]
      if (table[i + 1, j - 1] &&
          str[i] == str[j])
      {
        // Mark true
        table[i, j] = true;
 
        // Update the maximum length
        if (k > maxLength)
        {
          start = i;
          maxLength = k;
        }
      }
    }
  }
 
  // Return length of LPS
  return maxLength;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given String str
  String str = "forgeeksskeegfor";
 
  // Function Call
  Console.Write(longestPalSubstr(str));
}
}
 
// This code is contributed by Rajput-Ji

# Python program for the above approach
 
 
# Function to find the length of
# the longest palindromic subString
def longestPalSubstr(str):
    # Length of String str
    n = len(str);
 
    # Stores the dp states
    table = [[False for i in range(n)] for j in range(n)];
 
    # All subStrings of length 1
    # are palindromes
    maxLength = 1;
 
    for i in range(n):
        table[i][i] = True;
 
    # Check for sub-String of length 2
    start = 0;
 
    for i in range(n - 1):
 
        # If adjacent character are same
        if (str[i] == str[i + 1]):
            # Update table[i][i + 1]
            table[i][i + 1] = True;
            start = i;
            maxLength = 2;
 
    # Check for lengths greater than 2
    # k is length of subString
    for k in range(3, n + 1):
 
        # Fix the starting index
        for i in range(n - k + 1):
 
            # Ending index of subString
            # of length k
            j = i + k - 1;
 
            # Check for palindromic
            # subString str[i, j]
            if (table[i + 1][j - 1] and str[i] == str[j]):
 
                # Mark True
                table[i][j] = True;
 
                # Update the maximum length
                if (k > maxLength):
                    start = i;
                    maxLength = k;
 
    # Return length of LPS
    return maxLength;
 
 
# Driver Code
if __name__ == '__main__':
    # Given String str
    str = "forgeeksskeegfor";
 
    # Function Call
    print(longestPalSubstr(str));
 
# This code is contributed by 29AjayKumar

<script>
// javascript program for the above approach
 
    // Function to find the length of
    // the longest palindromic subString
    function longestPalSubstr(str) {
 
        // Length of String str
        var n = str.length;
 
        // Stores the dp states
        var table = Array(n).fill().map(()=>Array(n).fill(false));
         
        // All subStrings of length 1
        // are palindromes
        var maxLength = 1;
 
        for (var i = 0; i < n; ++i)
            table[i][i] = true;
 
        // Check for sub-String of length 2
        var start = 0;
 
        for (i = 0; i < n - 1; ++i) {
 
            // If adjacent character are same
            if (str.charAt(i) == str.charAt(i + 1)) {
 
                // Update table[i][i + 1]
                table[i][i + 1] = true;
                start = i;
                maxLength = 2;
            }
        }
 
        // Check for lengths greater than 2
        // k is length of subString
        for (k = 3; k <= n; ++k) {
 
            // Fix the starting index
            for (i = 0; i < n - k + 1; ++i) {
 
                // Ending index of subString
                // of length k
                var j = i + k - 1;
 
                // Check for palindromic
                // subString str[i, j]
                if (table[i + 1][j - 1] && str.charAt(i) == str.charAt(j)) {
 
                    // Mark true
                    table[i][j] = true;
 
                    // Update the maximum length
                    if (k > maxLength) {
                        start = i;
                        maxLength = k;
                    }
                }
            }
        }
 
        // Return length of LPS
        return maxLength;
    }
 
    // Driver Code
     
        // Given String str
        var str = "forgeeksskeegfor";
 
        // Function Call
        document.write(longestPalSubstr(str));
 
// This code is contributed by umadevi9616
</script>

10

Complejidad de tiempo: O(N ² ), donde N es la longitud de la string dada. 
Espacio Auxiliar: O(N) 

Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar el Algoritmo de Manacher . Al usar este algoritmo, para cada carácter c , se puede encontrar la substring palindrómica más larga que tiene c como su centro cuya longitud es impar. Pero la substring palindrómica más larga también puede tener una longitud uniforme que no tenga ningún centro. Por lo tanto, se pueden agregar algunos caracteres especiales entre cada carácter.

Por ejemplo, si la string dada es «abababc» , se convertirá en «$#a#b#a#b#a#b#c#@» . Ahora, observe que en este caso, para cada carácter c , la substring palindrómica más larga con el centro c tendrá una longitud impar.

A continuación se muestran los pasos: 

1. Agregue los caracteres especiales en la string dada S como se explicó anteriormente y deje que su longitud sea N .
2. Inicialice una array d[] , center y r con 0 donde d[i] almacena la longitud de la parte izquierda del palíndromo donde S[i] es el centro, r denota el límite visitado más a la derecha y center denota el índice actual de carácter que es el centro de este límite más a la derecha.
3. Mientras atraviesa la string S , para cada índice i , si i es más pequeño que r , entonces su respuesta se ha calculado previamente y d[i] se puede igualar para responder por el espejo del carácter en i con el centro que se puede calcular como (2*centro – i) .
4. Ahora, verifique si hay algunos caracteres después de r de modo que el palíndromo se vuelva cada vez más largo.
5. Si (i + d[i]) es mayor que r , actualice r = (i + d[i]) y centre como i .
6. Después de encontrar el palíndromo más largo para cada carácter c como centro, imprima el valor máximo de (2*d[i] + 1)/2 donde 0 ≤ i < N porque d[i] solo almacena la parte izquierda del palíndromo.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach:
#include <bits/stdc++.h>
using namespace std;
 
// Function that placed '#' intermediately
// before and after each character
string UpdatedString(string s){
 
  string newString = "#";
 
  // Traverse the string
  for(auto ch : s){
    newString += ch;
    newString += "#";
  }
 
  // Return the string
  return newString;
}
 
// Function that finds the length of
// the longest palindromic substring
int Manacher(string s){
 
  // Update the string
  s = UpdatedString(s);
 
  // Stores the longest proper prefix
  // which is also a suffix
  int LPS[s.length()] = {};
  int C = 0;
  int R = 0;
 
  for (int i = 0 ; i < s.length() ; i++){
    int imir = 2 * C - i;
 
    // Find the minimum length of
    // the palindrome
    if (R > i){
      LPS[i] = min(R-i, LPS[imir]);
    }
    else{
 
      // Find the actual length of
      // the palindrome
      LPS[i] = 0;
    }
 
    // Exception Handling
    while( ((i + 1 + LPS[i]) < s.length()) && ((i - 1 - LPS[i]) >= 0) && s[i + 1 + LPS[i]] == s[i - 1 - LPS[i]]){
      LPS[i] += 1;
    }
 
    // Update C and R
    if (i + LPS[i] > R){
      C = i;
      R = i + LPS[i];
    }
  }
 
  int r = 0, c = -1;
  for(int i = 0 ; i < s.length() ; i++){
    r = max(r, LPS[i]);
    if(r == LPS[i]){
      c = i;
    }
  }
 
  // Return the length r
  return r;
}
 
// Driver code
int main()
{
 
  // Given string str
  string str = "forgeeksskeegfor";
 
  // Function Call
  cout << Manacher(str) << endl;
}
 
// This code is contributed by subhamgoyal2014.

# Python program for the above approach
 
# Function that placed '#' intermediately
# before and after each character
def UpdatedString(string):
 
    newString = ['#']
 
# Traverse the string
    for char in string:
        newString += [char, '#']
 
# Return the string
    return ''.join(newString)
 
# Function that finds the length of
# the longest palindromic substring
def Manacher(string):
 
    # Update the string
    string = UpdatedString(string)
 
    # Stores the longest proper prefix
    # which is also a suffix
    LPS = [0 for _ in range(len(string))]
    C = 0
    R = 0
 
    for i in range(len(string)):
        imir = 2 * C - i
 
        # Find the minimum length of
        # the palindrome
        if R > i:
            LPS[i] = min(R-i, LPS[imir])
        else:
 
            # Find the actual length of
            # the palindrome
            LPS[i] = 0
 
        # Exception Handling
        try:
            while string[i + 1 + LPS[i]] \
            == string[i - 1 - LPS[i]]:
                LPS[i] += 1
        except:
            pass
 
        # Update C and R
        if i + LPS[i] > R:
            C = i
            R = i + LPS[i]
 
    r, c = max(LPS), LPS.index(max(LPS))
 
    # Return the length r
    return r
 
 
# Driver code
 
# Given string str
str = "forgeeksskeegfor"
 
# Function Call
print(Manacher(str))

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function that placed '#' intermediately
  // before and after each character
  static string UpdatedString(string s){
 
    string newString = "#";
 
    // Traverse the string
    foreach(char ch in s){
      newString += ch;
      newString += "#";
    }
 
    // Return the string
    return newString;
  }
 
  // Function that finds the length of
  // the longest palindromic substring
  static int Manacher(string s){
 
    // Update the string
    s = UpdatedString(s);
 
    // Stores the longest proper prefix
    // which is also a suffix
    int[] LPS = new int[s.Length];
    int C = 0;
    int R = 0;
 
    for (int i = 0 ; i < s.Length ; i++){
      int imir = 2 * C - i;
 
      // Find the minimum length of
      // the palindrome
      if (R > i){
        LPS[i] = Math.Min(R-i, LPS[imir]);
      }
      else{
 
        // Find the actual length of
        // the palindrome
        LPS[i] = 0;
      }
 
      // Exception Handling
      while( ((i + 1 + LPS[i]) < s.Length) &&
            ((i - 1 - LPS[i]) >= 0) &&
            s[i + 1 + LPS[i]] == s[i - 1 - LPS[i]]){
        LPS[i] += 1;
      }
 
      // Update C and R
      if (i + LPS[i] > R){
        C = i;
        R = i + LPS[i];
      }
    }
 
    int r = 0;
    for(int i = 0 ; i < s.Length ; i++){
      r = Math.Max(r, LPS[i]);
    }
 
    // Return the length r
    return r;
  }
 
  // Driver code
  public static void Main(string[] args){
 
    // Given string str
    string str = "forgeeksskeegfor";
 
    // Function Call
    Console.WriteLine(Manacher(str));
 
  }
}
 
// This code is contributed by entertain2022.

10

Complejidad de tiempo: O(N), donde N es la longitud de la string dada. 
Espacio Auxiliar: O(N)