Problem:
Given a string , find the longest palindromic substring in that string.
For example , for the input “babad”
the longest palindromic substring is “bab” or “aba”.
For the input “cbbd” the longest palindromic substring is “bb”
Assumptions:
- The string has at least one character and at the most 1000 characters
- The string consists of digits and English letters
Try out the solution here:
https://leetcode.com/problems/longest-palindromic-substring/
Solution:
Hint:
For every character , find if the left and right characters match and keep expanding the palindromic window for odd palindromes (length of the palindrome is odd)
For every two characters , find if the left and right characters match and keep expanding the palindromic window for even palindromes
ALGORITHM:
STEP 1: If the string consists of a single character return it
STEP 2: For ever character check for odd and even palindrome substrings
STEP 2a: For odd palindromes , check if the left and right characters to the current character match , if so keep expanding the window and track the window starting index and its length if it is greater than already found out windows
STEP 2b: For even palindromes , check if the left and right characters to the current character and its next character match , if so keep expanding the window and track the window length like the previous step.
STEP 3: Return the maximum window using the window start index and its length.
Code:
class Solution { int maxLeft = 0; int maxLen = 0; public String longestPalindrome(String s) { if(s.length() ==1 ) return s; char[] array = s.toCharArray(); for(int i=0;i<s.length();i++){ check(array,i,i); //odd palindromes check(array,i,i+1); //even palindromes } return s.substring(maxLeft, maxLeft+ maxLen); } void check(char[] s,int i,int j){ while(i>=0 && j < s.length && s[i] == s[j]){ i--; j++; } if(maxLen < j-i-1){ maxLeft = i+1; maxLen = j-i-1; } } }
In the above code while calculating the starting window index we do
maxLeft = i + 1
because while expanding the window in the previous step we land at one character behind because of the incrementing.
Similarly while calculation the max length , we do
maxLen = j - i +1
because we land at one character behind for the start and one character more for the end while incrementing and decrementing in the previous step.
That’s it!