Cut a word into pieces that each read the same backwards

Backtracking Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
word = "abba"
print([word[i:j] for i in range(len(word))
       for j in range(i + 2, len(word) + 1)
       if word[i:j] == word[i:j][::-1]])

Options

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

Show answer

Answer: A ['abba', 'bb']

Right: the only longer mirror slices are the whole word and the middle pair.

Those two slices plus single letters give the three cuttings of 'abba': four singles, 'a bb a', and the whole word.

Why not the others?
  • B ['bb']. The whole word also reads the same backwards.
  • C ['a', 'b', 'b', 'a', 'abba', 'bb']. Single letters are excluded by starting j at i + 2.

30-second answer

Try every first piece that reads the same backwards, then recurse on the rest of the word. Shorter first pieces come first, which yields sorted output. There can be 2ⁿ⁻¹ cuttings of length up to n (for 'aaaa…'), so O(n · 2ⁿ) is the worst case, and apart from the output the recursion takes O(n) space. A table of which slices read the same backwards removes the repeated checks.

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

Explain cutting a word into mirror pieces.

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

  • Try each valid first piece
  • Recurse on the rest
  • O(n · 2ⁿ) worst case

Deep dive

The 'first piece, then the rest' split is the template for all cutting questions.

Precomputing a mirror table costs O(n²) and makes each check O(1).

For 'fewest cuts' only, switch to DP; listing needs backtracking.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def mirror_cuts(word: str) -> list[list[str]]:
    out: list[list[str]] = []
    pieces: list[str] = []

    def cut(start: int) -> None:
        if start == len(word):
            out.append(pieces[:])
            return
        for end in range(start + 1, len(word) + 1):
            piece = word[start:end]
            if piece == piece[::-1]:  # reads the same backwards
                pieces.append(piece)
                cut(end)
                pieces.pop()

    cut(0)
    return out

Common mistakes

  • Recursing on the whole word instead of the remainder.
  • Forgetting the single-letter pieces, which always qualify.

Senior take & follow-ups

Say the split rule first, then mention the table as the optimisation.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find the fewest cuts?

    Show hint

    DP over prefixes with the mirror table: O(n²).

  2. How many cuttings does 'aaaa' have?

    Show hint

    8, one for every pattern of cut points.

What each operation costs: Depth First Search

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.