Palindrome Problems — Expand Around Center, DP, and Manacher Variants

Problem and Topic Statement#

The palindrome family includes a handful of canonical interview problems built on the same primitive — checking whether a substring reads the same forward and backward.

1. Longest Palindromic Substring (LC 5) — given s, return its longest palindromic substring.
2. Palindromic Substrings (LC 647) — count how many palindromic substrings exist in s.
3. Longest Palindromic Subsequence (LC 516) — find the longest palindromic subsequence (not contiguous).
4. Palindrome Partitioning II (LC 132) — minimum cuts to partition s such that every part is a palindrome.

These problems trade three weapons against each other: expand-around-center, 2D dynamic programming, and Manacher's linear-time algorithm. Picking the right tool for the question is half the interview.

Why This Topic Matters#

Palindromes are a perennial FAANG favourite. Meta, Google, Amazon, Microsoft, and Bloomberg all use Longest Palindromic Substring and Palindrome Partitioning in onsite loops because the problem family stress-tests three skills: recognising overlapping subproblems, choosing dimensionality of state, and identifying when an O(n^2) DP can be replaced by an O(n) algorithm such as Manacher.

In production, palindrome detection is a subroutine in DNA palindrome hunting where genomic regulatory sites form inverted repeats, search-engine query normalisation, and homoglyph-spoof detection. The algorithmic ideas — center expansion, mirror reflection, two-pointer comparison — recur in suffix automata, the Z-algorithm, and the Eertree palindromic tree.

Beyond mechanics, palindrome problems teach a planning skill: when the brute force is O(n^3), can you knock off a factor of n by storing prefix information? When the DP is O(n^2), can you prune by noting that a palindrome's interior must also be a palindrome? Recognising those compressions is the FAANG signal.

The Core Insight#

A palindrome of length L has two structures: even-length where the center sits between two characters, and odd-length where the center sits on a character. Every palindrome can be enumerated by walking through 2n minus 1 possible centers and expanding outward while characters match. That gives O(n^2) time.

Expand Around Center. For each index i, expand both an odd center at i and an even center between i and i+1, growing while s[left] == s[right]. Track the longest. The counting variant simply increments a counter per successful expansion step. This is the cleanest approach for both LC 5 and LC 647.

Bottom-up 2D DP. Define dp[i][j] = true if s[i..j] is a palindrome. Recurrence: dp[i][j] = (s[i] == s[j]) and (j - i lt 2 or dp[i+1][j-1]). Fill by increasing length. O(n^2) time and space, but extends naturally to Palindrome Partitioning.

Manacher. Transforms expand-around-center into O(n) by reusing previously computed expansions through a mirror trick. Use this when the interviewer presses for sub-quadratic.

For Longest Palindromic Subsequence (LC 516), the recurrence changes because you can skip characters: dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j], else max(dp[i+1][j], dp[i][j-1]). It is the same recurrence as LCS between s and reversed(s).

For Palindrome Partitioning II, precompute is_palin[i][j] in O(n^2), then run a 1D DP cuts[i] where cuts[i] is the minimum cuts to partition s[0..i]. The transition: cuts[i] = min(cuts[j-1] + 1) for every j where is_palin[j][i] is true.

Visual Dry Run / Worked Example#

Run expand-around-center on s = "babad":

i=0: odd "b" -> "b" (len 1)
i=1: odd "a" -> "bab" (len 3)
     even "ba" no
i=2: odd "b" -> "aba" (len 3)
     even "ab" no
i=3: odd "a" -> "a"
i=4: odd "d" -> "d"

Best is bab or aba, length 3.

For Palindrome Partitioning II of aab:

is_palin: dp[0][0]=T, dp[1][1]=T, dp[2][2]=T, dp[0][1]=T (aa), dp[1][2]=F, dp[0][2]=F (aab)
cuts[0] = 0  (a is palindrome)
cuts[1] = 0  (aa is palindrome)
cuts[2] = min(cuts[0]+1=1, cuts[1]+1=1) = 1

Answer: 1 cut, partitioning aa plus b.

Solution (Optimal)#

Longest Palindromic Substring (LC 5) — Expand Around Center (Python)#

def longestPalindrome(s):
    if not s:
        return ""
    start, end = 0, 0
 
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1
 
    for i in range(len(s)):
        l1, r1 = expand(i, i)
        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[start:end + 1]

Longest Palindromic Substring — JavaScript#

function longestPalindrome(s) {
  if (!s) return "";
  let start = 0, end = 0;
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return [l + 1, r - 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 = l1; end = r1; }
    if (r2 - l2 > end - start) { start = l2; end = r2; }
  }
  return s.slice(start, end + 1);
}

Complexity: O(n^2) time, O(1) extra space.

Palindrome Partitioning II (LC 132) — Min Cuts (Python)#

def minCut(s):
    n = len(s)
    is_palin = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or is_palin[i + 1][j - 1]):
                is_palin[i][j] = True
 
    cuts = [0] * n
    for i in range(n):
        if is_palin[0][i]:
            cuts[i] = 0
            continue
        cuts[i] = i
        for j in range(1, i + 1):
            if is_palin[j][i]:
                cuts[i] = min(cuts[i], cuts[j - 1] + 1)
    return cuts[n - 1]

Palindrome Partitioning II — JavaScript#

function minCut(s) {
  const n = s.length;
  const isPalin = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (s[i] === s[j] && (j - i < 2 || isPalin[i + 1][j - 1])) {
        isPalin[i][j] = true;
      }
    }
  }
  const cuts = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    if (isPalin[0][i]) { cuts[i] = 0; continue; }
    cuts[i] = i;
    for (let j = 1; j <= i; j++) {
      if (isPalin[j][i]) cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
    }
  }
  return cuts[n - 1];
}

Complexity: O(n^2) time, O(n^2) space.

Common Mistakes#

• Forgetting even-length palindromes. Many candidates only expand odd centers. You must also expand between i and i+1.
• Returning length instead of substring. Track start and end indices, not just the running maximum length.
• Comparing reversed string for LPS. Returning the longest common substring of s and reversed(s) is wrong because it can return a non-palindromic match like in abacdfgdcaba. You need an extra check that index intervals align.
• Overusing 2D DP when expand-around-center is cleaner. DP is O(n^2) space; center expansion is O(1).
• Skipping the precomputed is_palin in Partitioning II. Recomputing palindrome checks inside the cut DP gives O(n^3) and times out.

Interview Tips#

Open with the brute force: O(n^3) by enumerating all substrings and checking each. Then sharpen to expand-around-center. Always articulate odd-versus-even centers explicitly — interviewers note candidates who forget even centers.

For Longest Palindromic Subsequence, immediately link it to LCS — interviewers love hearing the reduction. For Palindrome Partitioning II, the key insight is precomputing is_palin so cut DP is O(n^2) overall.

If pushed for sub-quadratic on Longest Palindromic Substring, name Manacher's algorithm. You will not be expected to implement Manacher from scratch in 30 minutes, but knowing it exists and roughly how it reuses mirror reflections is FAANG-level signal.

Follow-up Questions#

1. Can you achieve O(n) for Longest Palindromic Substring? Yes — Manacher's algorithm.
2. Count palindromic subsequences (not substrings) — 2D DP with inclusion-exclusion.
3. Find the shortest palindrome you can build by prepending characters to s (LC 214) — KMP failure function on s + '#' + reversed(s).
4. Can the same character appear multiple times across partitions? Yes; partition treats positions, not character identity.
5. What if you allow at most k character mismatches in the palindrome? The recurrence becomes 3D: dp[i][j][k].

Key Takeaways#

• The palindrome family reduces to one core operation — expanding from a center while characters match.
• Always handle even and odd centers separately; forgetting even centers is the most common bug.
• Use expand-around-center for substring problems, 2D DP for partitioning, and reduce subsequence variants to LCS against the reversed string.
• Precompute is_palin tables in O(n^2) before DP cuts; otherwise the algorithm degrades to O(n^3).
• Manacher upgrades to O(n) but is rarely required in interviews; stating that you know it exists is enough signal.
• Across FAANG interviews, fluency with this family is more valuable than memorising any single solution because it generalises to a dozen variants.