Last Updated: 17 Nov, 2020
Longest Palindromic Substring
Moderate
Asked in companies
Given a string ’S’ consisting of lower case English letters, you are supposed to return the longest palindromic substring of ‘S’.
Note that in case of more than one longest palindromic substrings with the same length you need to return the rightmost substring in the given string. For example in string “bbbab”, there are two possible longest palindromic substrings i.e. “bbb” and “bab”, and since you are supposed to return the rightmost substring, so you need to return “bab” as the answer.
Note:
A substring is a contiguous sequence of elements within a string (for example, “bcd” is a substring of “abcde” while “bce” is not).
A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.
The only line of each test case contains a single string ‘S’ consisting of only lowercase English letters.
Output Format:
For each test case, print a single string in a single line denoting the longest palindromic substring of string ‘S’.
The output for each test case is in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 100
Where ‘N’ is the length of the string.
Time limit: 1 sec
Approaches
The brute force solution is to pick all possible starting and ending positions for a substring and verify if it is a palindrome.
The steps are as follows:
- If the length of the given string is zero, return an empty string. Else,
- Start checking each substring of the given string ‘S’ whether the substring is a palindrome or not.
- To do this first, run the two nested loops.
- These two loops pick up all the substrings one by one which can be done by fixing the corner characters.
- And inside the two loops, we are checking whether the picked substring is a palindrome or not.
- Now to check if the selected substring is palindrome or not, we are sending the starting and ending indexes of our selected substring in function isPalindrome() which returns ‘true’ if it’s a palindrome, otherwise, it returns ‘false’.
To improve our brute force solution, we first observe how we can avoid unnecessary re-computation while we are validating if a substring is a palindrome or not. Consider the case "xyzyx". Assume if we already know that "yzy" is a palindrome, then it seems obvious that "xyzyx" must be a palindrome since the two left and right end letters are the same.
The time complexity can be reduced by storing the prior results of its subproblems.
The steps are as follows:
- If the length of the given string is zero, then return an empty string. Else,
- Now we make a boolean ‘DP[N][N]’ for storing the result of each substring, where ‘N’ is the length of the given string ‘S’.
- Any element in the ‘DP’ matrix, say ‘DP[i][j]’ represents whether a substring starting from ‘i’th index and ending at the ‘j’th index of the given string is a palindrome or not. The value of ‘DP[i][j]’ is “true” if the substring is a palindrome, otherwise “false”.
- To calculate ‘DP[i][j]’, we check the value of ‘DP[i + 1][j - 1]’, if the value is “true” and ‘S[i]’ is the same as ‘S[j]’, then we make ‘DP[i][j]’ “true”.
- Else, the value of ‘DP[i][j]’ is made “false”.
- Prior to the computations of a substring with length greater than 2, we have to fill ‘DP’ matrix for a substring of length one and two because sometimes for corner positions (i+1) and (j-1) doesn’t exist between [0, ‘N’ - 1] range of the given string.
When you observe closely you will realise that a palindrome has mirrors around its centre, a palindrome can be expanded in both directions from its centre.
The steps are as follows:
- If the length of the given string is zero, then return an empty string. Else,
- Considering the mirror phenomenon there are 2 * ‘N’ - 1 such centre that we need to consider.
- Now you might be wondering why there are 2 * ‘N’ - 1 but not ‘N’ centres? The reason is that the centre of a palindrome can be in between two letters of the given string as well.
- there are ‘N’ - 1 space in the given string of length ‘N’ from which an even length palindrome can be computed
- while the palindromes originating with each element of the given string constitute ‘N’ possibilities of an odd length palindrome.
For example, in a string “abbab” of length 5, there are 5 possibilities that a palindrome can originate from the 5 indexes, so there are 5 substrings: “a”, “b”, “b”, “bab”, and “b” respectively (These are the longest palindromic substrings possible originating from each index of the string). All these accounts for an odd length palindrome.
Now, what about even length palindromes? Since there are 4 spaces in between the 5 characters of the given string, so the longest palindromic substrings possible originating from each space of the given string are “”, “abba”, “”, and “” respectively.
Now out of all these 9 possibilities, the longest palindromic substring is “abba”.
We keep on expanding the palindrome considering these centres as the centre of each substring, and simultaneously we keep on validating if the substring originating from each centre is a palindrome or not.
Similar problems