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 {
public:
    string result;
    int mxLength = INT_MIN;
    void checkPalindrome(string str, int start, int end){

        while(start>=0 && end<str.size() && str[start]==str[end]){
            start--;
            end++;
        }
        start = start+1;
        end = end - 1;

        int length = end-start+1;
        if(mxLength<length){
            mxLength = length;
            result = str.substr(start,length);
        }
    }
    string longestPalindrome(string str) {
        
        for(int i=0;i<str.size();i++){

            checkPalindrome(str,i,i);
            if(i!=str.size()-1)
                checkPalindrome(str,i,i+1);
        }
        return result;
    }
};

Approach 2: Dynamic Programming

class Solution {
public:
    string longestPalindrome(string str) {

        int n = str.size();
        string ans;
        int t[n][n];
        int head = 0;
        int mxLength = 1;

        // Initialize the DP table to 0
        memset(t, 0, sizeof(t));

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

            if(str[i]==str[i+1]){
                t[i][i+1] = 1;
                head = i;
                mxLength = 2;
            }
            else
                t[i][i+1] = 0;
        }
        
        for(int sz=3;sz<=n;sz++){
            for(int start=0;start<=n-sz;start++){

                int end = sz+start-1;
                if(str[start]==str[end] && t[start+1][end-1]==1){
                    t[start][end] = 1;
                    head = start;
                    mxLength = sz;
                }
            }
        }
        ans = str.substr(head,mxLength);
        return ans;
        
    }
};

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.

C++: Longest Palindromic Substring