Abstract / Summary

Print a string using the fewest steps where each step prints a substring containing one character and all its duplicates.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (200k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “Strange Printer” problem by defining a recursive helper deeper that computes the minimum number of turns needed to print a substring of s. The outer method strangePrinter simply invokes this helper on the whole string. Memoization is applied through the @cache decorator, which stores results of previously computed sub-problems and prevents redundant work.

Core Logic

The recursion works on three parameters: the original string (named what but never used inside the function), and the left and right indices that delimit the current substring. The first step inside deeper checks for an empty or invalid range:

if left > right:
    return 0

When the range is valid, the character at the leftmost position is taken as the current “stamp”:

stamp = s[left]

The algorithm then collapses any consecutive occurrences of this stamp at the beginning and at the end of the substring. This trimming step reduces the problem size without affecting the answer:

while left < right and s[left + 1] == stamp:
    left += 1
while left < right and s[right] == stamp:
    right -= 1

If after trimming only a single character remains, the answer is trivially one turn:

if left == right:
    return 1

The main recursive exploration starts by assuming the leftmost character will be printed in a separate turn, then solving the remainder of the substring:

best = 1 + deeper(what, left + 1, right)

The algorithm then looks for any other occurrence of the same stamp inside the trimmed interval. For each such occurrence, it splits the problem into two independent parts: the segment before the matching character and the segment after it. The total turns for this split is the sum of the optimal solutions for the two parts, and the minimum across all splits is kept:

for i in range(left + 1, right):
    if s[i] == stamp:
        a = deeper(what, left, i - 1)
        b = deeper(what, i + 1, right)
        best = min(best, a + b)

Finally, the best value is returned and propagated up the call stack:

return best

The outer method simply forwards the original string and the full index range to the helper:

return deeper(s, 0, len(s) - 1)

Edge Cases Handled

When the input string is empty, the initial call to deeper receives left = 0 and right = -1. The guard if left > right returns zero, correctly indicating that no printing turns are required.

If the string consists of a single repeated character, the trimming loops collapse the entire interval to a single position, triggering the if left == right branch and returning one turn.

When the substring contains multiple identical characters that are not contiguous, the loop that searches for matching stamps creates splits that allow those characters to be printed in a shared turn, thereby handling non-adjacent repetitions efficiently.

Performance Optimizations

The use of the @cache decorator provides memoization for the recursive function. Each distinct pair of (left, right) indices is evaluated at most once, turning the exponential explosion of naive recursion into a tractable number of sub-problem evaluations.

The early trimming of leading and trailing characters that match the current stamp reduces the depth of recursion and the number of distinct sub-problems. By eliminating redundant characters before the main recursion, the algorithm avoids unnecessary calls that would otherwise compute the same result multiple times.

The split strategy that only considers positions where the stamp reappears ensures that the recursion explores only meaningful partitions. This selective splitting prevents the algorithm from evaluating partitions that cannot improve the current best value, thereby cutting down the search space.

Imagine a magical printer that wants to create a long string of letters, one block at a time. This printer has a special trick where it can stamp a whole line of the same letter at once. The code acts like a little brain that looks at all the letters needed and figures out the quickest way to finish the job without wasting any time. It starts by looking at the first letter and notices if any neighbors are the same because it can print those together in one go. If the printer sees the same letter again later in the line, it thinks about whether it would be faster to pause and print that part in a different way. It keeps checking smaller and smaller groups of letters, trying every possible move to see which one uses the fewest steps. By remembering the solutions to groups it has already finished, the computer avoids doing the same work twice and eventually finds the very best secret shortcut to print everything perfectly.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java				Python	TS
	WalkCCC	C++		Java
	leetcode.ca	C++		Java			Go	Python	TS
	LeetcodeHelp	C++		Java				Python
	Progiez	C++		Java				Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	gouthampradhan			Java
	JoshCrozier		JS
	keineahnung2345	C++
	lzl124631x	C++
	ruoru				Rust
	suxrobGM					C#
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality