Dada una string S , la tarea de cada índice de la string es encontrar la longitud de la substring palindrómica más larga que comienza o termina en ese índice.
Ejemplos:
Entrada: S = “bababa”
Salida: 5 5 3 3 5 5
Explicación:
La substring palindrómica más larga que comienza en el índice 0 es “babab”. Por lo tanto, longitud = 5
La substring palindrómica más larga que comienza en el índice 1 es «ababa». Por lo tanto, length = 5
La substring palindrómica más larga que termina en el índice 2 es “bab”. Por lo tanto, length = 3
La substring palindrómica más larga que termina en el índice 3 es “aba”. Por lo tanto, length = 3
La substring palindrómica más larga que termina en el índice 4 es “babab”. Por lo tanto, longitud = 5
La substring palindrómica más larga que termina en el índice 5 es «ababa». Por lo tanto, longitud = 5Entrada: S = “aaa”
Salida: 3 2 3
Explicación:
La substring palindrómica más larga que comienza en el índice 0 es “aaa”. Por lo tanto, longitud = 3
La substring palindrómica más larga que comienza en el índice 1 es «ab». Por lo tanto, longitud = 2
La substring palindrómica más larga que termina en el índice 3 es: “aaa”. Por lo tanto, longitud = 3
Enfoque: la idea para resolver este problema es atravesar la string y, para cada índice, verificar la substring palindrómica más larga que se puede formar con ese índice, ya sea como el índice inicial y el índice final de la substring palindrómica. Siga los pasos a continuación para resolver el problema:
- Inicialice una array palLength[] para almacenar la longitud de las substrings palindrómicas más largas para cada índice.
- Recorra la string usando una variable i y realice las siguientes operaciones:
- Inicialice una variable, digamos maxLength , para almacenar la longitud de la substring palindrómica más larga para cada índice.
- Considere i como el índice final de una substring palindrómica y encuentre el primer índice de j sobre el rango [0, i – 1] , tal que S[j, i] es un palíndromo . Actualizar maxLength .
- Considere i como el índice de inicio de una substring palindrómica y encuentre el último índice de j sobre el rango [N – 1, i + 1] , tal que S[i, j] es un palíndromo . Actualizar maxLength .
- Almacene la longitud máxima obtenida al almacenar el valor de maxLength en palLength[i].
- Después de completar los pasos anteriores, imprima la array palLength[] como resultado.
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 return true if
// S[i...j] is a palindrome
bool isPalindrome(string S, int i, int j)
{
// Iterate until i < j
while (i < j)
{
// If unequal character encountered
if (S[i] != S[j])
return false;
i++;
j--;
}
// Otherwise
return true;
}
// Function to find for every index,
// longest palindromic substrings
// starting or ending at that index
void printLongestPalindrome(string S, int N)
{
// Stores the maximum palindromic
// substring length for each index
int palLength[N];
// Traverse the string
for (int i = 0; i < N; i++)
{
// Stores the maximum length
// of palindromic substring
int maxlength = 1;
// Consider that palindromic
// substring ends at index i
for (int j = 0; j < i; j++)
{
// If current character is
// a valid starting index
if (S[j] == S[i])
{
// If S[i, j] is palindrome,
if (isPalindrome(S, j, i))
{
// Update the length of
// the longest palindrome
maxlength = i - j + 1;
break;
}
}
}
// Consider that palindromic
// substring starts at index i
for (int j = N - 1; j > i; j--)
{
// If current character is
// a valid ending index
if (S[j] == S[i])
{
// If str[i, j] is palindrome
if (isPalindrome(S, i, j))
{
// Update the length of
// the longest palindrome
maxlength = max(j - i + 1, maxlength);
break;
}
}
}
// Update length of the longest
// palindromic substring for index i
palLength[i] = maxlength;
}
// Print the length of the
// longest palindromic substring
for (int i = 0; i < N; i++)
{
cout << palLength[i] << " ";
}
}
// Driver Code
int main()
{
string S = "bababa";
int N = S.length();
printLongestPalindrome(S, N);
return 0;
}
// This code is contributed by Kingash.
Java
// Java program for the above approach
class GFG {
// Function to find for every index,
// longest palindromic substrings
// starting or ending at that index
public static void
printLongestPalindrome(String S,
int N)
{
// Stores the maximum palindromic
// substring length for each index
int palLength[] = new int[N];
// Traverse the string
for (int i = 0; i < N; i++) {
// Stores the maximum length
// of palindromic substring
int maxlength = 1;
// Consider that palindromic
// substring ends at index i
for (int j = 0; j < i; j++) {
// If current character is
// a valid starting index
if (S.charAt(j) == S.charAt(i)) {
// If S[i, j] is palindrome,
if (isPalindrome(S, j, i)) {
// Update the length of
// the longest palindrome
maxlength = i - j + 1;
break;
}
}
}
// Consider that palindromic
// substring starts at index i
for (int j = N - 1; j > i; j--) {
// If current character is
// a valid ending index
if (S.charAt(j) == S.charAt(i)) {
// If str[i, j] is palindrome
if (isPalindrome(S, i, j)) {
// Update the length of
// the longest palindrome
maxlength = Math.max(j - i + 1,
maxlength);
break;
}
}
}
// Update length of the longest
// palindromic substring for index i
palLength[i] = maxlength;
}
// Print the length of the
// longest palindromic substring
for (int i = 0; i < N; i++) {
System.out.print(palLength[i] + " ");
}
}
// Function to return true if
// S[i...j] is a palindrome
public static boolean isPalindrome(
String S, int i, int j)
{
// Iterate until i < j
while (i < j) {
// If unequal character encountered
if (S.charAt(i) != S.charAt(j))
return false;
i++;
j--;
}
// Otherwise
return true;
}
// Driver Code
public static void main(String[] args)
{
String S = "bababa";
int N = S.length();
printLongestPalindrome(S, N);
}
}
Python3
# Python program for the above approach # Function to return true if # S[i...j] is a palindrome def isPalindrome(S, i, j): # Iterate until i < j while (i < j): # If unequal character encountered if (S[i] != S[j]): return False i += 1 j -= 1 # Otherwise return True # Function to find for every index, # longest palindromic substrings # starting or ending at that index def printLongestPalindrome(S, N): # Stores the maximum palindromic # substring length for each index palLength = [0 for i in range(N)] # Traverse the string for i in range(N): # Stores the maximum length # of palindromic substring maxlength = 1 # Consider that palindromic # substring ends at index i for j in range(i): # If current character is # a valid starting index if (S[j] == S[i]): # If S[i, j] is palindrome, if (isPalindrome(S, j, i)): # Update the length of # the longest palindrome maxlength = i - j + 1 break # Consider that palindromic # substring starts at index i j = N-1 while(j > i): # If current character is # a valid ending index if (S[j] == S[i]): # If str[i, j] is palindrome if (isPalindrome(S, i, j)): # Update the length of # the longest palindrome maxlength = max(j - i + 1, maxlength) break j -= 1 # Update length of the longest # palindromic substring for index i palLength[i] = maxlength # Print the length of the # longest palindromic substring for i in range(N): print(palLength[i],end = " ") # Driver Code if __name__ == '__main__': S = "bababa" N = len(S) printLongestPalindrome(S, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to return true if
// S[i...j] is a palindrome
static bool isPalindrome(string S, int i, int j)
{
// Iterate until i < j
while (i < j)
{
// If unequal character encountered
if (S[i] != S[j])
return false;
i++;
j--;
}
// Otherwise
return true;
}
// Function to find for every index,
// longest palindromic substrings
// starting or ending at that index
static void printLongestPalindrome(string S, int N)
{
// Stores the maximum palindromic
// substring length for each index
int[] palLength = new int[N];
// Traverse the string
for (int i = 0; i < N; i++)
{
// Stores the maximum length
// of palindromic substring
int maxlength = 1;
// Consider that palindromic
// substring ends at index i
for (int j = 0; j < i; j++)
{
// If current character is
// a valid starting index
if (S[j] == S[i])
{
// If S[i, j] is palindrome,
if ((isPalindrome(S, j, i)) != false)
{
// Update the length of
// the longest palindrome
maxlength = i - j + 1;
break;
}
}
}
// Consider that palindromic
// substring starts at index i
for (int j = N - 1; j > i; j--)
{
// If current character is
// a valid ending index
if (S[j] == S[i])
{
// If str[i, j] is palindrome
if (isPalindrome(S, i, j))
{
// Update the length of
// the longest palindrome
maxlength = Math.Max(j - i + 1, maxlength);
break;
}
}
}
// Update length of the longest
// palindromic substring for index i
palLength[i] = maxlength;
}
// Print the length of the
// longest palindromic substring
for (int i = 0; i < N; i++)
{
Console.Write(palLength[i] + " ");
}
}
// Driver Code
static public void Main ()
{
string S = "bababa";
int N = S.Length;
printLongestPalindrome(S, N);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for the above approach
// Function to return true if
// S[i...j] is a palindrome
function isPalindrome(S, i, j) {
// Iterate until i < j
while (i < j) {
// If unequal character encountered
if (S[i] !== S[j]) return false;
i++;
j--;
}
// Otherwise
return true;
}
// Function to find for every index,
// longest palindromic substrings
// starting or ending at that index
function printLongestPalindrome(S, N) {
// Stores the maximum palindromic
// substring length for each index
var palLength = new Array(N);
// Traverse the string
for (var i = 0; i < N; i++) {
// Stores the maximum length
// of palindromic substring
var maxlength = 1;
// Consider that palindromic
// substring ends at index i
for (var j = 0; j < i; j++) {
// If current character is
// a valid starting index
if (S[j] === S[i]) {
// If S[i, j] is palindrome,
if (isPalindrome(S, j, i) !== false) {
// Update the length of
// the longest palindrome
maxlength = i - j + 1;
break;
}
}
}
// Consider that palindromic
// substring starts at index i
for (var j = N - 1; j > i; j--) {
// If current character is
// a valid ending index
if (S[j] === S[i]) {
// If str[i, j] is palindrome
if (isPalindrome(S, i, j)) {
// Update the length of
// the longest palindrome
maxlength = Math.max(j - i + 1, maxlength);
break;
}
}
}
// Update length of the longest
// palindromic substring for index i
palLength[i] = maxlength;
}
// Print the length of the
// longest palindromic substring
for (var i = 0; i < N; i++) {
document.write(palLength[i] + " ");
}
}
// Driver Code
var S = "bababa";
var N = S.length;
printLongestPalindrome(S, N);
</script>
Producción:
5 5 3 3 5 5
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)