Dada una string S , la tarea es encontrar la substring más larga que es un palíndromo
. Ejemplos:
Entrada: S = “aaaabbaa”
Salida: 6
Explicación:
La substring “aabbaa” es la substring palindrómica más larga.
Entrada: S = “banana”
Salida: 5
Explicación:
La substring “anana” es la substring palindrómica más larga.
Enfoque: La idea es utilizar la recursividad para dividir el problema en subproblemas más pequeños. Para dividir el problema en dos subproblemas más pequeños, compare los caracteres de inicio y final de la string y llame recursivamente a la función para la substring del medio. A continuación se muestra la ilustración de la recursividad:
- Caso base: el caso base de este problema es cuando el índice inicial de la string es mayor o igual que el índice final.
if (start > end)
return count
if (start == end)
return count + 1
- Caso recursivo: compare los caracteres en el índice inicial y final de la string:
- Cuando los caracteres de inicio y final son iguales, llame recursivamente a la substring excluyendo los caracteres de inicio y final
recursive_func(string, start+1, end-1)
- Cuando los caracteres iniciales y finales no son iguales, llame recursivamente a la substring excluyendo los caracteres iniciales y finales uno a la vez.
recursive_func(string, start+1, end) recursive_func(string, start, end-1)
- Declaración de devolución: en cada llamada recursiva, devuelva el recuento máximo posible incluyendo y excluyendo los caracteres de inicio y finalización.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// length of longest palindromic
// sub-string using Recursion
#include <iostream>
using namespace std;
// Function to find maximum
// of the two variables
int max(int x, int y)
{
return (x > y) ? x : y;
}
// Function to find the longest
// palindromic substring : Recursion
int longestPalindromic(string str,
int i, int j, int count)
{
// Base condition when the start
// index is greater than end index
if (i > j)
return count;
// Base condition when both the
// start and end index are equal
if (i == j)
return (count + 1);
// Condition when corner characters
// are equal in the string
if (str[i] == str[j]) {
// Recursive call to find the
// longest Palindromic string
// by excluding the corner characters
count = longestPalindromic(str, i + 1,
j - 1, count + 2);
return max(count,
max(longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0)));
}
// Recursive call to find the
// longest Palindromic string
// by including one corner
// character at a time
return max(
longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0));
}
// Function to find the longest
// palindromic sub-string
int longest_palindromic_substr(string str)
{
// Utility function call
return longestPalindromic(str, 0,
str.length() - 1, 0);
}
// Driver Code
int main()
{
string str = "aaaabbaa";
// Function Call
cout << longest_palindromic_substr(str);
return 0;
}
Java
// Java implementation to find the
// length of longest palindromic
// sub-String using Recursion
class GFG{
// Function to find maximum
// of the two variables
static int max(int x, int y)
{
return (x > y) ? x : y;
}
// Function to find the longest
// palindromic subString : Recursion
static int longestPalindromic(String str,
int i, int j, int count)
{
// Base condition when the start
// index is greater than end index
if (i > j)
return count;
// Base condition when both the
// start and end index are equal
if (i == j)
return (count + 1);
// Condition when corner characters
// are equal in the String
if (str.charAt(i) == str.charAt(j)) {
// Recursive call to find the
// longest Palindromic String
// by excluding the corner characters
count = longestPalindromic(str, i + 1,
j - 1, count + 2);
return max(count,
max(longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0)));
}
// Recursive call to find the
// longest Palindromic String
// by including one corner
// character at a time
return Math.max(
longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0));
}
// Function to find the longest
// palindromic sub-String
static int longest_palindromic_substr(String str)
{
// Utility function call
return longestPalindromic(str, 0,
str.length() - 1, 0);
}
// Driver Code
public static void main(String[] args)
{
String str = "aaaabbaa";
// Function Call
System.out.print(longest_palindromic_substr(str));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find the # length of longest palindromic # sub-string using Recursion # Function to find maximum # of the two variables def maxi(x, y) : if x > y : return x else : return y # Function to find the longest # palindromic substring : Recursion def longestPalindromic(strn, i, j, count): # Base condition when the start # index is greater than end index if i > j : return count # Base condition when both the # start and end index are equal if i == j : return (count + 1) # Condition when corner characters # are equal in the string if strn[i] == strn[j] : # Recursive call to find the # longest Palindromic string # by excluding the corner characters count = longestPalindromic(strn, i + 1, j - 1, count + 2) return maxi(count, maxi(longestPalindromic(strn, i + 1, j, 0), longestPalindromic(strn, i, j - 1, 0))) # Recursive call to find the # longest Palindromic string # by including one corner # character at a time return maxi( longestPalindromic(strn, i + 1, j, 0), longestPalindromic(strn, i, j - 1, 0)) # Function to find the longest # palindromic sub-string def longest_palindromic_substr(strn): # Utility function call k = len(strn) - 1 return longestPalindromic(strn, 0, k, 0) strn = "aaaabbaa" # Function Call print( longest_palindromic_substr(strn) ) # This code is contributed by chsadik99
C#
// C# implementation to find the
// length of longest palindromic
// sub-String using Recursion
using System;
class GFG{
// Function to find maximum
// of the two variables
static int max(int x, int y)
{
return (x > y) ? x : y;
}
// Function to find the longest
// palindromic subString : Recursion
static int longestPalindromic(String str,
int i, int j, int count)
{
// Base condition when the start
// index is greater than end index
if (i > j)
return count;
// Base condition when both the
// start and end index are equal
if (i == j)
return (count + 1);
// Condition when corner characters
// are equal in the String
if (str[i] == str[j]) {
// Recursive call to find the
// longest Palindromic String
// by excluding the corner characters
count = longestPalindromic(str, i + 1,
j - 1, count + 2);
return max(count,
max(longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0)));
}
// Recursive call to find the
// longest Palindromic String
// by including one corner
// character at a time
return Math.Max(
longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0));
}
// Function to find the longest
// palindromic sub-String
static int longest_palindromic_substr(String str)
{
// Utility function call
return longestPalindromic(str, 0,
str.Length - 1, 0);
}
// Driver Code
public static void Main(String[] args)
{
String str = "aaaabbaa";
// Function Call
Console.Write(longest_palindromic_substr(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find the
// length of longest palindromic
// sub-String using Recursion
// Function to find maximum
// of the two variables
function max(x, y)
{
return (x > y) ? x : y;
}
// Function to find the longest
// palindromic subString : Recursion
function longestPalindromic(str, i, j, count)
{
// Base condition when the start
// index is greater than end index
if (i > j)
return count;
// Base condition when both the
// start and end index are equal
if (i == j)
return (count + 1);
// Condition when corner characters
// are equal in the String
if (str[i] == str[j]) {
// Recursive call to find the
// longest Palindromic String
// by excluding the corner characters
count = longestPalindromic(str, i + 1,
j - 1, count + 2);
return max(count,
max(longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0)));
}
// Recursive call to find the
// longest Palindromic String
// by including one corner
// character at a time
return Math.max(
longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0));
}
// Function to find the longest
// palindromic sub-String
function longest_palindromic_substr(str)
{
// Utility function call
return longestPalindromic(str, 0, str.length - 1, 0);
}
let str = "aaaabbaa";
// Function Call
document.write(longest_palindromic_substr(str));
// This code is contributed by mukesh07.
</script>
Producción:
6
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA