Pattern 3: Two Pointers and expand from the center

A palindrome is a word that reads the same backward: racecar, level. Two pointers converging from the ends verify a palindrome; two pointers diverging from a center find all of them.

Tried it? A common approach is to "clean" the string (strip punctuation, lowercase it) and compare it with its reverse — it works, but spends O(n) memory. The theory below does the same with two pointers and O(1) space.

Theory 1: checking with converging pointers

The definition of a palindrome is symmetric: the 1st char must equal the last, the 2nd the second-to-last, and so on up to the middle. That's literally the two pointers from the Array section, on a string:

left = 0; right = n - 1
while left < right:
    if s[left] != s[right]: not a palindrome
    left += 1; right -= 1
it's a palindrome

Why stop in the middle (left < right)? Because once they cross, all the symmetric pairs have already been checked — continuing would just repeat the comparisons. O(n) time (each char is visited once), O(1) space.

Example 1 — Valid Palindrome

"Is the string a palindrome, considering only letters/digits and ignoring case?" E.g.: "A man, a plan, a canal: Panama" → true.

The palindrome logic is the same; the twist is skipping what doesn't count. Instead of cleaning the string up front (spending O(n) memory), the two pointers simply jump over non-alphanumeric characters as they converge — keeping space at O(1).

Watch the pointers converging on an already-cleaned string (focus on the pattern):

Even with the inner while loops skipping characters, each pointer traverses the string once in total — O(n), O(1) space (cleaning the string up front would cost O(n) memory).

Theory 2: finding palindromes by expanding from the center

Now the inverse problem: how many / what's the longest palindrome inside a string. Brute force tests all substrings and verifies each one — O(n²) substrings × O(n) verification = O(n³).

The waste: each verification starts from scratch, ignoring that palindromes have structure. The insight: every palindrome has a center, and it grows symmetrically out from it. So, instead of testing substrings, pick each possible center and expand two pointers outward while the sides match:

for each center:
    left, right = center
    while within bounds and s[left] == s[right]:
        found a palindrome!
        left -= 1; right += 1

An essential detail: there are two types of center. Odd-length palindromes have their center at a character (aba, center b); even-length ones have their center between two characters (abba, center between the two bs). That's why we expand twice from each position.

Example 2 — Palindromic Substrings

"How many palindromic substrings are there?" ("aaa" → 6: three a, two aa, one aaa). Each successful expansion is a palindrome — so you just count:

Why is it O(n²)?

There are n center positions (actually ~2n, counting odd and even), and each expansion costs at most O(n). Centers × expansion = O(n²) time, with O(1) space. We went from brute force's O(n³) down to O(n²) by eliminating the re-verification waste — and O(n²) is expected for "examining palindromes", since the answer can have size O(n²).

Example 3 — Longest Palindromic Substring

The exact same technique: expand from each center and, instead of counting, keep the longest palindrome found (its start/end positions). Swapping "count" for "record the maximum" is the only difference — again, the pattern is the same, only what you harvest changes. O(n²) time, O(1) space.

There's Manacher's algorithm, which solves it in O(n). It's clever and rarely required — expanding from the center (O(n²)) passes the vast majority of cases and is what you should master first.

Summary

• Checking a palindrome: converging two pointers, O(n)/O(1); skip irrelevant chars with the pointers themselves to keep O(1).
• Finding palindromes: expand from the center, considering odd and even centers — O(n²)/O(1), much better than the naive O(n³).
• Counting or finding the longest use the same expansion; only what you harvest changes.

Next lesson: the structure that handles nesting and matching of symbols — the stack.