Count the stretches that read the same backwards

Strings and tries Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
text = "aaa"
count = 0
for centre in range(2 * len(text) - 1):
    lo, hi = centre // 2, centre // 2 + centre % 2
    while 0 <= lo and hi < len(text) and text[lo] == text[hi]:
        count += 1
        lo, hi = lo - 1, hi + 1
print(count)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 6

Right: three single letters, two 'aa' and one 'aaa'.

Counting by position means repeats such as the two 'aa' stretches both count, which the centre walk handles naturally.

Why not the others?
  • B 3. The gaps between letters are centres too.
  • C 4. Each 'aa' is counted at its own position.

30-second answer

Expand around each of the 2n - 1 centres, adding one for every step where the ends still match. Every qualifying substring has exactly one centre, so each is counted once. O(n²) time, O(1) memory.

Practise saying it · 30 s. No recording, just a timer

Explain counting mirror substrings.

Say your answer out loud, then check which of these points you covered:

  • Expand around centres
  • Add one per matching step
  • O(n²)

Deep dive

Same expansion as finding the longest; only the bookkeeping changes.

For 'aaaa', every substring qualifies: n(n + 1) / 2.

A DP table of 'is s[i:j] a mirror' also works in O(n²) time but O(n²) memory.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def count_mirrors(text: str) -> int:
    total = 0
    for centre in range(2 * len(text) - 1):  # letters and gaps
        lo, hi = centre // 2, centre // 2 + centre % 2
        while 0 <= lo and hi < len(text) and text[lo] == text[hi]:
            total += 1  # text[lo:hi + 1] reads the same backwards
            lo, hi = lo - 1, hi + 1
    return total

Common mistakes

  • Counting only odd lengths.
  • Counting distinct strings when the question counts positions.

Senior take & follow-ups

State that every qualifying substring has exactly one centre; that proves no double counting.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you count distinct ones instead?

    Show hint

    Collect them in a set while expanding (each expansion adds at most one new string per step).

  2. Can this be done in O(n)?

    Show hint

    Yes, with Manacher's algorithm, summing (radius + 1) // 2 over centres.

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.