Longest Palindromic Substring

Every palindrome mirrors around its center. A string with n characters has exactly 2n - 1 possible symmetry points: n single characters and n - 1 gaps between adjacent characters. Expanding outward from each candidate center discovers the longest local palindrome, and the global maximum among them is the overall answer.

Full solution

Expand around centers: check all 2n-1 symmetry points (n single characters, n-1 gaps) in O(n^2) time with O(1) space, avoiding the O(n^2) table the DP approach needs.

def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    start, end = 0, 0

    def expand(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for i in range(len(s)):
        l1, r1 = expand(i, i)      # odd length, center on i
        l2, r2 = expand(i, i + 1)  # even length, center between i and i+1
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2

    return s[start:end + 1]

function longestPalindrome(s) {
  if (!s) return "";

  let start = 0;
  let end = 0;

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

  for (let i = 0; i < s.length; i++) {
    const [l1, r1] = expand(i, i);
    const [l2, r2] = expand(i, i + 1);
    if (r1 - l1 > end - start) [start, end] = [l1, r1];
    if (r2 - l2 > end - start) [start, end] = [l2, r2];
  }

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

The theory behind it

Strings — the ground this problem stands on. All Strings problems

What Strings is

A string is an ordered necklace of text characters, like letters printed along a ribbon of paper. Each character sits at an exact numeric slot, holding a glyph such as a letter, punctuation mark, or digit. In many programming languages, ribbons cannot be edited after creation, meaning changing a single character requires pressing an entirely new ribbon from scratch.

When to reach for it

Reach for string techniques when inputs consist of words, DNA sequences, serialized data formats, or sentences. Clues include questions testing palindromes, anagram matches, substring patterns, parenthesis balancing, or character frequency counts. Whenever an algorithm asks to transform capitalization, parse structured tokens, or compute edits between two phrases, string representations are the core subject.

How the pattern works

Think of characters as small integer codes ranging across standard character sets. Frequency tables with fixed sizes often replace heavy hash maps when tallying occurrences. For search tasks, maintain rolling state using character indices or sliding borders. When building output text through repeated appends, accumulate pieces inside a mutable list or string builder rather than concatenating strings directly, avoiding quadratic copy overhead.