Longest Palindromic Substring

Problem statement

Given a string s, return one longest substring that reads the same forwards and backwards. If several share that length, any of them is fine.

Example:

Input:

s = "babad"

Expected output:

"bab"

"aba" is also correct. "babad" itself is not a palindrome.

Practice on LeetCode: Longest Palindromic Substring

What we are filling in

A substring is contiguous, so every candidate is a pair of indices (i, j).

dp[i][j] means: is s[i…j] a palindrome?

A one-letter string always is. Two letters are a palindrome only when they match ("bb", not "ba"). Anything longer is a palindrome only when the ends match and the inside already is one:

s[i] == s[j]  and  s[i+1 … j-1] is a palindrome

That is why the table is filled by increasing length. Length 3 reads length 1. Length 4 reads length 2. You never ask about a cell you have not written yet.

On "babad":

          0b  1a  2b  3a  4d
     0b    Y   .   Y   .   .
     1a        Y   .   Y   .
     2b            Y   .   .
     3a                Y   .
     4d                    Y

"bab" and "aba" both become Y at length 3. Nothing longer works. The code keeps the last longest it sees, so it returns "aba".

Why not check every substring

There are O(n²) substrings. Scanning each one from both ends is another O(n). That is O(n³). LeetCode lets n hit 1000. A billion character looks will time out.

The DP asks a constant-time question per pair once the shorter answers exist: O(n²) time, O(n²) space.

Golang Solution

Mark every single character. Then every adjacent pair. Then grow diff from 2 to n-1 (j = i + diff). When a cell is a palindrome, record [i, j]. Because length only increases, the last record is a longest answer.

Time: O(n²)
Space: O(n²)

func longestPalindrome(s string) string {
    n := len(s)
    dp := make([][]bool, n)
    for i := range n {
        dp[i] = make([]bool, n)
    }
    ans := []int{0, 0}

    for i := 0; i < n; i++ {
        dp[i][i] = true
    }
    for i := 0; i < n-1; i++ {
        if s[i] == s[i+1] {
            dp[i][i+1] = true
            ans = []int{i, i + 1}
        }
    }

    for diff := 2; diff < n; diff++ {
        for i := 0; i < n-diff; i++ {
            j := i + diff
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
                ans = []int{i, j}
            }
        }
    }

    i, j := ans[0], ans[1]
    return s[i : j+1]
}

ans starts at {0, 0} because a non-empty string always has a length-1 palindrome. You do not need a separate “max length” variable: a later diff is a longer window.

Expand-around-center solves the same problem in O(n²) time and O(1) extra space — same time, no table. The DP is the version that makes the recurrence obvious.