Given a string S, the task for every index of the string is to find the length of the longest palindromic substring that either starts or ends at that index.
Examples:
Input: S = “bababa”
Output: 5 5 3 3 5 5
Explanation:
Longest palindromic substring starting at index 0 is “babab”. Therefore, length = 5
Longest palindromic substring starting at index 1 is “ababa”. Therefore, length = 5
Longest palindromic substring ending at index 2 is “bab”. Therefore, length = 3
Longest palindromic substring ending at index 3 is “aba”. Therefore, length = 3
Longest palindromic substring ending at index 4 is “babab”. Therefore, length = 5
Longest palindromic substring ending at index 5 is “ababa”. Therefore, length = 5Input: S = “aaa”
Output: 3 2 3
Explanation:
Longest palindromic substring starting at index 0 is “aaa”. Therefore, length = 3
Longest palindromic substring starting at index 1 is “ab”. Therefore, length = 2
Longest palindromic substring ending at index 3 is: “aaa”. Therefore, length = 3
Approach: The idea to solve this problem is to traverse the string and for each index, check for the longest palindromic substring that can be formed with that index either as the starting index and the ending index of the palindromic substring. Follow the steps below to solve the problem:
- Initialize an array palLength[] to store the length of the longest palindromic substrings for each index.
- Traverse the string using a variable i and perform the following operations:
- Initialize a variable, say maxLength, to store the length of the longest palindromic substring for each index.
- Consider i to be the ending index of a palindromic substring and find the first index from j over the range [0, i – 1], such that S[j, i] is a palindrome. Update maxLength.
- Consider i as the starting index of a palindromic substring and find the last index from j over the range [N – 1, i + 1], such that S[i, j] is a palindrome. Update maxLength.
- Store the maximum length obtained by storing the value of maxLength in palLength[i].
- After completing the above steps, print the array palLength[] as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return true if// S[i...j] is a palindromebool 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 indexvoid 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 Codeint 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 approachclass 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 palindromedef 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 indexdef 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 Codeif __name__ == '__main__': S = "bababa" N = len(S) printLongestPalindrome(S, N) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;class GFG{// Function to return true if// S[i...j] is a palindromestatic 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 indexstatic 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 Codestatic 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> |
Output:
5 5 3 3 5 5
Time Complexity: O(N3)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
