Longest palindromic Subsequence

return longest palindrome

Longest Palindromic Substring

Problem

You are given a string s. Return the longest palindromic substring in s.

A palindrome reads the same from left to right and from right to left. A substring is a block of characters that sit next to each other.

Examples

Example 1

Input: s = "babad"
Output: "bab"

• "aba" is also a valid answer.

Example 2

Input: s = "cbbd"
Output: "bb"

Constraints

• 1 <= s.length <= 1000
• s has only digits and English letters.

Main Idea

Every palindrome has a center. If we start from the center and move outward, we can check how big the palindrome is.

• Move one step left and one step right.
• If both characters are equal, the palindrome grows.
• If they are different, or we reach the edge, we stop.

There are two kinds of centers:

• Odd length: The center is one character, like "aba". We start with l = i and r = i.
• Even length: The center is between two characters, like "abba". We start with l = i and r = i + 1.

For a string of length n, there are 2n - 1 centers. We try all of them and keep the longest result.

Brute Force (For Comparison)

We check every substring and test if it is a palindrome.

• There are about n² substrings, and each check takes up to O(n).
• Time Complexity: O(n³)
• Space Complexity: O(1)

This is slow, even for n = 1000.

Solution: Expand Around Center

var longestPalindrome = function (s) {
    let start = 0;
    let end = 0;

    // grow from the center and return the final palindrome range
    function expand(l, r) {
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            l--;
            r++;
        }

        // l and r are one step too far, so fix them
        return [l + 1, r - 1];
    }

    for (let i = 0; i < s.length; i++) {
        // odd length: center is one character
        let [l1, r1] = expand(i, i);

        // even length: center is between two characters
        let [l2, r2] = expand(i, i + 1);

        if (r1 - l1 > end - start) {
            start = l1;
            end = r1;
        }

        if (r2 - l2 > end - start) {
            start = l2;
            end = r2;
        }
    }

    return s.slice(start, end + 1);
};

How the Code Works

Step 1: Keep the best range

• start and end hold the range of the longest palindrome found so far.

Step 2: The expand function

• It starts with two pointers, l and r.
• While both are inside the string and s[l] === s[r], it moves them outward.
• The loop stops after one extra step, so we return [l + 1, r - 1].
• For an even center with different characters, like expand(i, i + 1) on "ab", the loop does not run. We return [i + 1, i], which is an empty range, and it never wins.

Step 3: Try every center

• For each index i, we try the odd center and the even center.
• If a range is longer than the best one, we save it.

Step 4: Return the answer

• s.slice(start, end + 1) gives the substring.

Dry Run

Let us take s = "babad".

The answer is "bab".

Complexity

• Time Complexity: O(n²)
  • There are 2n - 1 centers.
  • Each expansion takes up to O(n).
• Space Complexity: O(1)
  • We use only a few variables. The output string is not counted.

Comparison

Summary

• Every palindrome has a center, so we grow outward from each center.
• There are two center types: one