Longest Palindromic Substring

Thought Process

The Longest Palindromic Substring problem requires finding the longest substring that reads the same forwards and backwards. Here are two approaches:

Approach 1: Expand Around Center - Iterate through each character and treat it as the center of a potential palindrome. Expand around the center to check for the longest palindrome, considering both odd-length and even-length palindromes. Track the maximum length and the corresponding substring.

Approach 2: Dynamic Programming - Use a 2D DP table to store whether substrings are palindromes. Initialize the table for single-character and two-character palindromes. Fill the table for longer substrings, checking if endpoints match and inner substring is a palindrome. Track the longest palindrome during this process by comparing lengths when new palindromes are found.

Approach 1: Expand Around Center

class Solution {

    int mxLength = 0;
    String ans;

    // This will check how big palindrome we can make.
    public void checkPalindrome(String str, int start, int end){

        while(start>=0 && end<str.length() && str.charAt(start)== str.charAt(end)){
            start--;
            end++;
        }
        start = start+1;
        end = end - 1;
        int length = end-start+1;
        if(length>mxLength){
            mxLength = length;
            ans = str.substring(start,start+mxLength); // [a,b)
        }
    }
    public String longestPalindrome(String s) {
        
        int sz = s.length();
        for(int i=0;i<sz;i++){

            checkPalindrome(s,i,i); // Odd Length Palindrome
            if(i<sz-1)
                checkPalindrome(s,i,i+1); // Even Length Palindrome
        }
        return ans;
    }
}

Approach 2: Dynamic Programming

class Solution {
    public String longestPalindrome(String s) {

        int n = s.length();
        int[][] t = new int[n][n];
        int[] ans = new int[2];

        for(int i=0;i<n;i++)
            t[i][i] = 1;

        for(int i=0;i<n-1;i++){
            if(s.charAt(i)==s.charAt(i+1)){
                t[i][i+1]=1;
                ans[0] = i;
                ans[1] = i+1;
            }
        }

        for(int sz=3;sz<=n;sz++){
            for(int start=0;start<=n-sz;start++){ // start = n-1, sz=n
                
                int end = start+sz-1;
                if(t[start+1][end-1] == 1 && s.charAt(start)==s.charAt(end)){
                    t[start][end] = 1;
                    ans[0] = start;
                    ans[1] = end;
                }
            }
        }
        return s.substring(ans[0],ans[1]+1);
    }
}

Code Complexity

Time Complexity: O(n²)

Approach 1 iterates through the string and expands around each center, resulting in O(n²) time. Approach 2 uses a DP table, also resulting in O(n²) time.

Space Complexity: O(n²)

Approach 1 uses constant extra space, while Approach 2 uses a 2D DP table, resulting in O(n²) space.

Java: Longest Palindromic Substring