medium1D Dynamic Programming

Longest Palindromic Substring

Find the longest contiguous palindrome in a string. If several have the same maximum length, return the earliest.

LeetCode ↗

Work through the cases

3 examples

Input notation

One nonempty string.

Expected result

The selected substring.

Case 1

Input

cbbd

Expected output

bb

Case 2

Input

abac

Expected output

aba

Case 3

Input

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Checking every s[i..j] from the ends is O(n^3). n ≤ 10^3 is tight and often times out. The waste is rescanning each substring. A palindrome has optimal substructure: s[i..j] is a palindrome iff the two ends match and the inner s[i+1..j-1] already is one. Single characters are palindromes for free. So we fill an interval table in dependency order instead of scanning repeatedly. f[i][j] reads a shorter inner cell, so that cell must already be known; while filling, k and mx remember the start and length of the best palindrome so far.

We define f[i][j] to represent whether the string s[i..j] is a palindrome, initially f[i][j] = true.

Next, we define variables k and mx, where k represents the starting position of the longest palindrome, and mx represents the length of the longest palindrome. Initially, k = 0, mx = 1.

Considering f[i][j], if s[i] = s[j], then f[i][j] = f[i + 1][j - 1]; otherwise, f[i][j] = false. If f[i][j] = true and mx < j - i + 1, then we update k = i, mx = j - i + 1.

Since f[i][j] depends on f[i + 1][j - 1], we need to ensure that i + 1 is before j - 1, so we need to enumerate i from large to small, and enumerate j from small to large.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the string s.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        for (var g : f) {
            Arrays.fill(g, true);
        }
        int k = 0, mx = 1;
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = false;
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1];
                    if (f[i][j] && mx < j - i + 1) {
                        mx = j - i + 1;
                        k = i;
                    }
                }
            }
        }
        return s.substring(k, k + mx);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.