Last Updated: 20 Sep, 2020
Longest Palindromic Substring
Moderate
Asked in companies
You are given a string 'str' of length 'N'.
Your task is to return the longest palindromic substring. If there are multiple strings, return any.
A substring is a contiguous segment of a string.
For example :
str = "ababc"
The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome.
There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.
Input Format:
The first line contains a string 'str'.
Output Format :
The output contains the size of the longest palindromic substring if that substring is the answer, else -1.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Follow up:
Try to solve it using O(1) space complexity.
Approaches
- Generate substrings of the given string such that substring having greater length will be generated first.
- To do this, run a loop where iterator ‘LEN’ will go from N to 1, where N is the length of the given string.
- Run a nested loop and fix an iterator ‘j’ that will point at the starting index of the substring.
- Get the substring from ‘j’ to ‘j’ + ‘LEN’.
- If the substring is a palindrome, return the substring (as the substring will be of the longest length and minimum starting index).
- If the string length is less than or equal to 1 then return the string, as one length string is always palindromic.
- Initialize a ‘DP’ array of data type boolean, ‘DP’[i][j] will store false if STR[i, j] is not palindromic otherwise it will store true.
- Store all the diagonal elements (DP[i][i]) as true, as STR[i, i] will always be palindromic.
- For substring of length 2, check if STR[i] is equal to STR[i + 1] then store DP[i][i + 1] as true.
- Run a loop for the length of a substring greater than 2, fill the DP array diagonally.
- To calculate DP[i][j], check the value of DP[i + 1][j - 1], if the value is true and STR[i] is same as STR[j], then we make DP[i][j] true otherwise false.
- For every DP[i][j] true, update the length and starting index of the substring.
- Return the substring of the string having starting index as start and of maximum length.
- If the string length is less than or equal to 1 then return the string, as a single character is always palindromic.
- The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far. Run a loop where ‘i’ will be from 0 to ‘N’ - 1.
- To generate odd length palindrome, fix center ‘i’, and expand in both directions for longer palindromes. Odd length palindromes will have a character at the center.
- Similarly, for even length palindrome, fix the center as ‘i’, ‘i’ + 1, and expand in both directions. Even palindrome will have a partition between ith char and i+1th char as the center.
- If the length of the current palindromic substring length is greater then update the starting length of the string and length of the palindromic substring.
- Return the substring of the string having starting index as ‘START’ and of maximum length.
For expanding :
- For expanding around a center ‘i’ for odd length, initialize two variables ‘LEFT’ and ‘RIGHT’ to ‘i’ and go until ‘LEFT and ’RIGHT' are in range and STR[LEFT] == STR[RIGHT]. Decrement the ‘LEFT’ and increment the ‘RIGHT’.
- For expanding around a centre ‘i’ and ‘i’ + 1 for even length, initialise two variables ‘LEFT’ = ‘i’ and ‘RIGHT’ = ‘i’ + 1, and go until ‘LEFT’ and ‘RIGHT’ are in range and STR[LEFT] == STR[RIGHT]. Decrement the ‘LEFT’ and increment the ‘RIGHT’.
- Return the length of the palindromic substring.
Similar problems