DSA Roadmap/Advanced String Algorithms

Palindromic Substrings (Expand Around Center)

Recognize that every palindrome has a center, then expand outward from all 2n-1 of them — the single technique behind nearly every palindrome interview question.

!!!2/5Theory: 1h3 problems

Why expand-around-center is your default

A palindrome reads the same forwards and backwards, and almost every interview question about palindromic substrings — find the longest one, count them all, check if a small edit produces one — reduces to the same primitive: given a candidate center, how far can it expand before the string stops being symmetric around it? The O(n²) "expand around center" technique answers that question for every possible center in a string and is, on its own, sufficient to solve the large majority of palindrome interview questions cleanly. It's the default tool here — for the rarer case where an interviewer explicitly presses for linear time, see the Manacher's Algorithm subtopic in Advanced Niche Algorithms, which upgrades this exact idea to O(n).

Expand around center: the practical default

The key realization: every palindrome has a center

Every palindromic substring is uniquely determined by a center and a radius. But there are two kinds of centers, and missing this distinction is the single most common bug in this entire subtopic:

  • Odd-length palindromes ("aba", "level") are centered on a character.
  • Even-length palindromes ("abba", "noon") are centered between two characters.

For a string of length n, there are n odd centers and n - 1 even centers — 2n - 1 centers total. The algorithm is: for each of these 2n - 1 centers, expand outward while the characters on both sides match, and track whatever you're optimizing (longest length, total count, etc).

def expand_around_center(s, left, right): """Expands outward from (left, right) while it stays a palindrome. Returns the length of the palindrome found.""" while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return right - left - 1 # undo the last (failed) expansion def longest_palindromic_substring(s): if not s: return "" start, best_len = 0, 1 for i in range(len(s)): odd_len = expand_around_center(s, i, i) # odd-length centers even_len = expand_around_center(s, i, i + 1) # even-length centers local_best = max(odd_len, even_len) if local_best > best_len: best_len = local_best start = i - (local_best - 1) // 2 return s[start:start + best_len]

Calling the same expand_around_center helper for both center types — rather than writing two near-duplicate loops — is what keeps this clean under interview time pressure.

Complexity

Time: O(n²). There are O(n) centers, and each expansion can take O(n) in the worst case (e.g. "aaaaaaaa", where every center expands almost to the string's edges). Space: O(1) beyond the output — this is a meaningful advantage over the O(n²)-space DP formulation of the same problem (build a dp[i][j] table of "is s[i..j] a palindrome"), which solves the identical problem with the same time complexity but worse space, and is generally not the version you want to reach for first in an interview — expand-around-center gets you the same asymptotic time with a much smaller, more intuitive implementation.

The precomputed-table variant, and when you actually need it

The dp[i][j] formulation (dp[i][j] = True iff s[i..j] is a palindrome, filled by increasing substring length, using dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]) is worse than expand-around-center for a single "longest/count" query — but it earns its O(n²) space back the moment you need repeated, random-access palindrome checks on arbitrary substrings after the fact, most commonly when a problem asks you to partition a string into palindromic pieces (backtracking over cut points, checking "is this piece a palindrome?" over and over). Precomputing the table once up front turns each of those checks into O(1), instead of re-running expand-around-center (or a fresh s[i:j] == s[i:j][::-1]) on every candidate slice.

Pitfalls and interview gotchas

  • Forgetting even-length centers. Only checking odd centers (i, i) and never even ones (i, i+1) is the single most common bug in expand-around-center implementations — it silently misses every even-length palindrome ("bb", "abba").
  • Off-by-one when converting a radius back to a substring. After expand_around_center fails, left and right have both moved one step past the actual palindrome's boundaries — the valid palindrome is s[left+1:right], not s[left:right].
  • Treating "longest palindromic substring" and "longest palindromic subsequence" as the same problem. They are not: the subsequence version does not require contiguity and is solved with a completely different technique (classic 2-D string DP, covered under 2-D DP & String DP) — expand-around-center only applies to contiguous substrings.
  • Reaching past this into an O(n) algorithm by default. Given the difficulty-to-frequency ratio of a from-scratch linear-time implementation, defaulting to expand-around-center and only reaching for something faster when explicitly pressed for linear time is the better interview instinct — it's faster to write correctly under pressure, and in most rooms it's exactly the depth expected.

Where this connects

Expand-around-center is a direct application of the opposite-direction two-pointer discipline from Two Pointers — you're just choosing 2n - 1 different starting positions for the same "walk inward/outward while a condition holds" pattern instead of one. If you want the O(n) upgrade that reuses this exact idea, see Manacher's Algorithm in Advanced Niche Algorithms — it's a natural next stop once this subtopic feels solid, but it's genuinely optional depth for FAANG-style interviews.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.