Longest Palindromic Substring

Problem Statement

Constraints

Solution 1: Dynamic Programming

function longestPalindromeDP(s) {
    const n = s.length;
    if (n === 0) return "";

    let start = 0;
    let maxLength = 1;

    const dp = Array(n).fill(false).map(() => Array(n).fill(false));

    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            if (s[i] === s[j]) {
                if (length === 2) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] && length > maxLength) {
                    start = i;
                    maxLength = length;
                }
            }
        }
    }

    return s.substring(start, start + maxLength);
} 

const s1 = "babad";
longestPalindromeDP(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeDP(s2);  //output: bb 

Solution 2: Manachers Algorithm

function longestPalindromeManacher(s) {
    let t = "#" + s.split("").join("#") + "#";
    const n = t.length;
    const p = Array(n).fill(0);
    let center = 0;
    let right = 0;

    for (let i = 0; i < n; i++) {
        if (i < right) {
            p[i] = Math.min(right - i, p[2 * center - i]);
        }
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && t[i + p[i] + 1] === t[i - p[i] - 1]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }

    let maxLen = 0;
    let start = 0;
    for (let i = 0; i < n; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            start = i;
        }
    }

    return s.substring((start - maxLen) / 2, (start + maxLen) / 2);
} 

const s1 = "babad";
longestPalindromeManacher(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeManacher(s2);  //output: bb 

Solution 3: Expand Around Center with Memoization

function longestPalindromeExpandAroundCenterMemo(s) {
    const memo = new Map();

    function isPalindrome(left, right) {
        if (left > right) return true;
        if (memo.has(`${left},${right}`)) return memo.get(`${left},${right}`);
        const result = (left >= 0 && right < s.length && s[left] === s[right] && isPalindrome(left + 1, right - 1));
        memo.set(`${left},${right}`, result);
        return result;
    }

    let start = 0;
    let maxLength = 0;

    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            if (isPalindrome(i, j)) {
                if (j - i + 1 > maxLength) {
                    start = i;
                    maxLength = j - i + 1;
                }
            }
        }
    }

    return s.substring(start, start + maxLength);
} 

const s1 = "babad";
longestPalindromeExpandAroundCenterMemo(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeExpandAroundCenterMemo(s2);  //output: bb 

Solution 4: Longest Palindromic Substring with Two Pointers

function longestPalindromeTwoPointers(s) {
    if (s.length === 0) return "";

    let maxLen = 1;
    let start = 0;

    for (let i = 0; i < s.length; i++) {
        let l = i;
        let r = i;

        // Check for odd length palindromes
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            if (r - l + 1 > maxLen) {
                maxLen = r - l + 1;
                start = l;
            }
            l--;
            r++;
        }

        l = i;
        r = i + 1;

        // Check for even length palindromes
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            if (r - l + 1 > maxLen) {
                maxLen = r - l + 1;
                start = l;
            }
            l--;
            r++;
        }
    }

    return s.substring(start, start + maxLen);
} 

const s1 = "babad";
longestPalindromeTwoPointers(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeTwoPointers(s2);  //output: bb 

Solution 5: Using a Set for Palindromes

function longestPalindromeUsingSet(s) {
    const palindromes = new Set();

    function addPalindromes(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            palindromes.add(s.substring(left, right + 1));
            left--;
            right++;
        }
    }

    for (let i = 0; i < s.length; i++) {
        addPalindromes(i, i);
        addPalindromes(i, i + 1);
    }

    let longest = "";
    palindromes.forEach(palindrome => {
        if (palindrome.length > longest.length) {
            longest = palindrome;
        }
    });

    return longest;
} 

const s1 = "babad";
longestPalindromeUsingSet(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeUsingSet(s2);  //output: bb 

Solution 6: Recursive Approach

function longestPalindromeRecursive(s) {
    function isPalindrome(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }

    let longest = "";

    for (let i = 0; i < s.length; i++) {
        let pal1 = isPalindrome(i, i);
        let pal2 = isPalindrome(i, i + 1);
        let currentLongest = pal1.length > pal2.length ? pal1 : pal2;
        if (currentLongest.length > longest.length) {
            longest = currentLongest;
        }
    }

    return longest;
} 

const s1 = "babad";
longestPalindromeRecursive(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeRecursive(s2);  //output: bb 

Solution 7: Using a Stack for Palindrome Check

function longestPalindromeStack(s) {
    const stack = [];
    let longest = "";

    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            const substring = s.substring(i, j + 1);
            if (isPalindromeStack(substring)) {
                if (substring.length > longest.length) {
                    longest = substring;
                }
            }
        }
    }

    return longest;

    function isPalindromeStack(str) {
        const stack = [];
        for (let char of str) {
            stack.push(char);
        }
        let reversed = "";
        while (stack.length) {
            reversed += stack.pop();
        }
        return str === reversed;
    }
} 

const s1 = "babad";
longestPalindromeStack(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeStack(s2);  //output: bb 

Solution 8: Using Hash Map for Palindrome Check

function longestPalindromeHashMap(s) {
    const map = new Map();
    let longest = "";

    function isPalindrome(str) {
        if (map.has(str)) return map.get(str);
        const result = str === str.split("").reverse().join("");
        map.set(str, result);
        return result;
    }

    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            const substring = s.substring(i, j + 1);
            if (isPalindrome(substring)) {
                if (substring.length > longest.length) {
                    longest = substring;
                }
            }
        }
    }

    return longest;
} 

const s1 = "babad";
longestPalindromeHashMap(s1);  //output: bab 

const s2 = "cbbd";
longestPalindromeHashMap(s2);  //output: bb 

Frequently asked questions

1. What is the Longest Palindromic Substring problem about?

   The Longest Palindromic Substring problem requires you to identify and return the longest contiguous substring from a given string s that is a palindrome. A palindrome is a sequence that reads the same forwards and backwards.

2. How does the Dynamic Programming approach work?

   The Dynamic Programming solution constructs a 2D table to track which substrings are palindromes. By building up solutions for progressively larger substrings based on smaller ones, it efficiently finds the longest palindromic substring.

3. What is Manacher's Algorithm and how does it work?

   Manacher's Algorithm preprocesses the string by inserting special characters to handle even-length palindromes uniformly. It maintains an array that records the maximum radius of palindromes centered at each position, achieving linear time complexity.

4. How does the Recursive Approach work to find the longest palindromic substring?

   The Recursive Approach finds palindromes by expanding outward from each character or between characters and compares the length of the resulting palindromes. This approach is straightforward but can be less efficient due to its recursive nature.

More Problems Solutions