Room 04 · The Grind — 1-D Dynamic Programming

Longest Palindromic Substring

MEDIUM✓ CHIP-TIMEDLC #5 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Somewhere inside a string sits its longest run that reads the same forwards and backwards. Find that substring.

A string arrives, and somewhere inside it sits a contiguous run of characters that reads identically forwards and backwards — a palindrome.

Several different substrings might tie for the longest palindrome; any one of the longest is an acceptable answer, not a specific one among the ties.

The task is to return that substring itself — the actual run of characters, not its length or its position in the string.

string length can run into the low thousands
characters can include letters, digits, or other symbols
single characters count as palindromes of length one
when several longest palindromes tie, any one of them is acceptable

EX 01

s = "a"

→ "a"

minimum size, single character

EX 02

s = "xx"

→ "xx"

whole string is the palindrome

EX 03

s = "level"

→ "level"

whole string, odd length

The hintstake only what you need

HINT 1 THE NUDGE

Testing every substring for the palindrome property costs a scan per candidate on top of the count of candidates — where is the redundant work hiding?

HINT 2 THE STRUCTURE

A palindrome is built outward from its center — a single character, or a gap between two — and stops growing the instant its two ends disagree. Every palindrome has exactly one center.

HINT 3 ONE STEP FROM THE ANSWER

Walk every possible center (n single-character centers, n-1 between-character centers), expand outward while the ends match, and keep the widest span you've seen.

Coach's boardthe pattern, step by step

THE CENTER EXPANSIONPATTERN · EXPAND AROUND CENTERs = "banana"

BEST WINDOW SO FAR

— empty —

STEP 1

Every palindrome grows from a center — a single character or a gap. Walk each one, expanding while the ends still match.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/longest-palindromic-substring.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)

        def expand(l: int, r: int) -> tuple:
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            return l + 1, r - 1                  # last valid window

        start, end = 0, 0
        for i in range(n):
            l1, r1 = expand(i, i)                 # odd-length center
            if r1 - l1 > end - start:
                start, end = l1, r1
            l2, r2 = expand(i, i + 1)              # even-length center
            if r2 - l2 > end - start:
                start, end = l2, r2
        return s[start:end + 1]

TIME O(N^2)SPACE O(1)PYTHON · RACE PACE · 19 LN

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        best = s[0]
        for i in range(n):
            for j in range(i, n):
                candidate = s[i:j + 1]
                if len(candidate) > len(best) and candidate == candidate[::-1]:
                    best = candidate
        return best

TIME O(N^3)SPACE O(1)PYTHON · TRAINING PACE · 10 LN

class Solution {
    private int bestStart = 0, bestEnd = 0;

    public String longestPalindrome(String s) {
        bestStart = 0;
        bestEnd = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            expand(s, i, i);
            expand(s, i, i + 1);
        }
        return s.substring(bestStart, bestEnd + 1);
    }

    private void expand(String s, int l, int r) {
        int n = s.length();
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        l++;
        r--;
        if (r - l > bestEnd - bestStart) {
            bestStart = l;
            bestEnd = r;
        }
    }
}

TIME O(N^2)SPACE O(1)JAVA · RACE PACE · 28 LN

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String best = s.substring(0, 1);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String candidate = s.substring(i, j + 1);
                if (candidate.length() > best.length() && isPalindrome(candidate)) {
                    best = candidate;
                }
            }
        }
        return best;
    }

    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

TIME O(N^3)SPACE O(1)JAVA · TRAINING PACE · 27 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED