String Algorithms

Palindromes

Expand around centres or compare from both ends.

Medium, about 75 minutes to practise.

1Understand

The idea

A palindrome reads the same from both ends, so compare inward with two pointers. To find palindromic substrings, expand outward from every centre: each character, and each gap between two characters for even lengths. That gives O(n²) total with O(1) extra space.

Intuition

A palindrome reads the same forward and backward, so two pointers moving inward compare characters. For substrings, expand outward from every centre, each character (odd length) and each gap between characters (even length).

That expansion is O(n²) time and O(1) extra space, which beats generating all substrings explicitly. Manacher's algorithm is O(n) but rarely required.

Whole-string palindrome checks are the inward two-pointer special case.

What you will be able to do

  • Handle odd and even centres
  • Normalise case and non-alphanumerics when asked

When to use it

  • Longest palindromic substring
  • Is it a palindrome after removing one char?
  • Count palindromic substrings

2See it

Walkthrough

Expand around centers

s = "aba", odd center at index 1.

1 / 6

MLR
a
b
a
012
M → index 1

Try each center i. Odd: L=R=i.

L, R = i, i

Live template

Line 1 active

1def expand(l, r):
2 while l >= 0 and r < n and s[l] == s[r]: l -= 1; r += 1
3 return r - l - 1
4for c in range(n): best = max(best, expand(c, c), expand(c, c + 1))

Complexity: time O(n²), space O(1)

Expand-around-centre is O(n²) time, O(1) space. DP dp[i][j] is also O(n²) with O(n²) space. For only checking one string, two pointers are O(n).

Read the walkthrough as text

Longest palindromic substring. s = "babad".

  1. Expand from index 0 (b) → "b". From gap 0-1, no even palindrome.
  2. From index 1 (a): odd expand gives "bab"; record.
  3. From index 2 (b): "aba" also length 3.
  4. Answer "bab" or "aba".

In code:

- def expand(l, r): - while l >= 0 and r < n and s[l] == s[r]: - l -= 1; r += 1 - return s[l+1:r] Try all centres; keep the longest returned slice.

3Recognise it

Kinds of problems (6)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Valid palindrome (with normalisation)

    Example. Palindrome after stripping non-alphanumerics.

    How. Two pointers inward on filtered chars; skip or normalize case first.

  • Palindrome after one deletion

    Example. Can become palindrome by removing one char?

    How. Two pointers; on mismatch try skip left or skip right once.

  • Longest palindromic substring

    Example. Longest substring that reads the same both ways.

    How. Expand around each centre odd and even; track best span.

  • Count palindromic substrings

    Example. Number of palindromic substrings in s.

    How. Same expansion; each valid expand contributes 1 (or count centres).

  • Longest palindrome from letter counts

    Example. Longest palindrome built from multiset of chars.

    How. Use all pairs; at most one odd count char in centre.

  • Change one letter (break a palindrome)

    Example. Lex smallest palindrome strictly smaller than s.

    How. Find first position from left where s differs from reverse; decrement with carry rules.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Even centres missed

    Why it happens. Expand only at index i covers odd-length centres.

    How it fails. Longest even palindrome "abba" missed, only checked expand(i,i).

    Fix. Also expand(i,i+1) for each i.

  • Brute force

    Why it happens. Check every substring for correctness.

    How it fails. n=500: O(n³) substring checks time out on longest palindromic substring.

    Fix. Expand around centres O(n²) or Manacher.

  • No normalisation

    Why it happens. Compare raw chars when statement already says alphanumeric only.

    How it fails. "A man, a plan..." fails because spaces and case differ.

    Fix. Filter to alnum lower (or problem’s rule) before two-pointer check.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons