Length of longest palindromic sub-string : Recursion
Given a string S, the task is to find the length longest sub-string which is a palindrome
Examples:
Input: S = “aaaabbaa”
Output: 6
Explanation:
Sub-string “aabbaa” is the longest palindromic sub-string.
Input: S = “banana”
Output: 5
Explanation:
Sub-string “anana” is the longest palindromic sub-string.
Approach:The idea is to use recursion to break the problem into smaller sub-problems. In order to break the problem into two smaller sub-problems, Compare the start and end characters of the string and recursively call the function for the middle substring. Below is the illustration of the recursion:
- Base Case: The base case for this problem is when the starting index of the string is greater than or equal to the ending index.
if (start > end) return count if (start == end) return count + 1
- Recursive Case: Compare the characters at the start and end index of the string:
- When starting and ending characters are equal, then recursively call for the substring by excluding the starting and ending characters
recursive_func(string, start+1, end-1)
- When starting and ending characters are not equal, then recursively call for the substring by excluding the starting and ending characters one at a time.
recursive_func(string, start+1, end) recursive_func(string, start, end-1)
- Return statement: At each recursive call, return the maximum count possible by including and excluding the start and end characters.
Below is the implementation of above approach:
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> |
6
Time Complexity : The time complexity of this code is O(n^2) as there are two recursive calls in each iteration and the loop iterates over all characters of the string.
Auxiliary Space : The space complexity is O(n) as the recursive function calls consume space on the call stack.
Contact Us