LeetCode 647 · 1-D DP

Palindromic Substrings, explained with a picture

Counting every mirror image hidden in a word.

Medium1-D DP
▶ Watch it step by step

The problem

Count how many substrings (blocks of consecutive letters) of a string are palindromes. Blocks at different positions count separately.

Input:  "abaab"
Output: 8

Picture it

Same mirror trick: stand a mirror on every letter and between every pair of letters, then expand outward while the two sides match. Each successful expansion step is one more palindrome, so we add 1 to the count every time.

How to recognise it

  • You must count substrings with a symmetry property, and substrings at different positions count separately ("aaa" has 6).
  • A palindrome is symmetric about its centre, and shrinking one by a letter on each side leaves a palindrome.
  • The string has up to 1,000 characters, so O(n²) is fine and O(n³) is borderline.
  • The count can reach n(n + 1)/2, so you want a method that adds one per palindrome found, not one that lists them.

Start with brute force

Look at every substring and test whether it equals its reverse.

def count_brute(s):
    n = len(s); total = 0
    for i in range(n):
        for j in range(i, n):
            piece = s[i:j + 1]
            if piece == piece[::-1]:
                total += 1
    return total

There are n(n + 1)/2 substrings and each test costs up to O(n), so time is O(n³): about 1.7 × 10^8 character comparisons for n = 1,000 (and more once slicing is counted). Space is O(n) for the slice.

From brute force to the idea

  1. Find the waste. Testing s[i:j+1] ignores that its inside, s[i+1:j], was already known to be a palindrome or not.
  2. Grow from the centre. Take a centre and widen l and r while s[l] == s[r]. Every successful widening is a new palindrome.
  3. Two kinds of centre. Odd palindromes centre on a letter, (c, c); even ones centre between letters, (c, c + 1). That makes 2n − 1 centres.
  4. Count each step. Each time the ends match, add 1 to count before widening. The first step counts the centre itself, the second the palindrome one letter wider, and so on until the match fails.

This is the key idea: every palindromic substring is found exactly once, as one step of the expansion from its own centre.

The key idea

Expand around every centre and count each successful step. O(n²).

Python solution

def count_substrings(s):
    count = 0
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):   # odd and even centres
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l, r = l - 1, r + 1
    return count

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n³): n² substrings, each compared in O(n)O(n): the slice being tested
Expand around centres (shown code)O(n²): 2n − 1 centres, each expands at most n/2 steps (worst for aaaa…)O(1): a counter and two indices

Edge cases

  • Empty string: returns 0.
  • One letter ("a"): returns 1.
  • All different ("abc"): returns 3, only the single letters.
  • All the same ("aaa"): returns 6; "a" * 1000 returns 500500, which equals n(n + 1)/2 and is the largest possible count.
  • Even palindrome ("abba"): returns 6 (four letters, "bb" and "abba").
  • Repeated text counted separately ("abab"): returns 6; "a" and "b" each count twice, and "aba" and "bab" once each.

Common mistakes

  • Using only odd centres, so "abba" gives 4 instead of 6.
  • Counting distinct palindromes (a set of strings) instead of every occurrence, which is a different problem.
  • Adding to count after the loop instead of inside it, so each centre contributes at most 1.
  • Skipping the bounds check, giving IndexError or wrong matches through negative indices.
Your turn: ignore single letters

Count only the palindromic substrings of length 2 or more. For "aaa" the answer is 3 ("aa" twice and "aaa"). Describe your approach, then write it if you like.

Compare with our answer

The same expansion works. Only a palindrome with at least two letters should be counted, which means r > l at the moment of counting.

def count_long(s):
    count = 0
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r > l:
                    count += 1
                l, r = l - 1, r + 1
    return count

count_long("aaa") is 3 and count_long("abba") is 2. Time O(n²), space O(1). (Subtracting n from the original answer gives the same number.)

A strong answer mentions: both kinds of centre, counting inside the loop, the r > l test (or subtracting n, since every single letter is a palindrome), and the O(n²) worst case.

Check what stuck

1. You must count how many substrings of a 1,000-character string are palindromes, counting repeats at different positions. Which approach fits best?

2. What is the time complexity of the shown code, and when is it worst?

3. What does the shown code return for "aaa"?

Score 60% or more and the lesson is marked complete.