Data Structures & Algorithms in Java – Strings – Longest Palindromic Substring

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!