LeetCode 664: Strange Printer

Problem Restatement

We are given a string s.

There is a strange printer with two rules:

The printer can choose any continuous segment of the string in one turn.

Return the minimum number of turns needed to print the whole string.

For example, to print:

s = "aba"

we can first print:

aaa

Then overwrite the middle character with:

b

So the answer is 2. The statement details match LeetCode 664: the printer prints a sequence of the same character and may overwrite existing characters.

Input and Output

Example function shape:

def strangePrinter(s: str) -> int:
    ...

Examples

Consider:

s = "aaabbb"

We can print "aaa" in one turn and "bbb" in another turn.

So the answer is:

2

Now consider:

s = "aba"

One optimal plan is:

Turn 1: print "aaa"
Turn 2: print "b" at the middle position

So the answer is:

2

Another example:

s = "abc"

Each character is different. We need one turn for each character:

a
b
c

So the answer is:

3

First Thought: Print Groups

A natural idea is to print each consecutive group separately.

For example:

s = "aaabbb"

has two groups:

aaa
bbb

So the answer is 2.

But this does not always capture the best strategy.

For:

s = "aba"

there are three groups:

a
b
a

A group-based strategy would say 3, but the real answer is 2.

The printer can overwrite characters, so matching characters that are separated may still be printed together.

Key Insight

This is an interval dynamic programming problem.

Let:

dp[i][j]

mean:

the minimum number of turns needed to print s[i:j+1]

The answer is:

dp[0][n - 1]

For one character:

dp[i][i] = 1

because a single character needs one print turn.

For a longer substring, we can start with a safe choice:

print s[j] separately after printing s[i:j]

That gives:

dp[i][j] = dp[i][j - 1] + 1

But if there is an earlier position k where:

s[k] == s[j]

then the turn that prints s[k] can also print s[j].

That may save one turn.

Recurrence

For every substring s[i:j+1], initialize:

dp[i][j] = dp[i][j - 1] + 1

Then try every k from i to j - 1.

If:

s[k] == s[j]

then we can combine the printing of s[k] and s[j].

The candidate cost is:

dp[i][k] + dp[k + 1][j - 1]

So:

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1])

The middle part s[k+1:j] must still be printed separately, but the final s[j] does not require its own new turn.

Algorithm

1. Let n = len(s).
2. Create an n x n DP table.
3. Set all dp[i][i] = 1.
4. Process substrings by increasing length.
5. For each substring s[i:j+1]:
   • Start with dp[i][j - 1] + 1.
   • Try every split position k.
   • If s[k] == s[j], merge the print turn for those matching characters.
6. Return dp[0][n - 1].

Correctness

The state dp[i][j] considers only the substring from index i to index j.

For a single-character substring, one turn is necessary and sufficient.

For a longer substring, printing s[j] in a separate final turn after printing s[i:j] is always valid, so dp[i][j - 1] + 1 is a correct upper bound.

If some earlier character s[k] equals s[j], then the printer can use the same turn that prints s[k] to also print s[j], because a turn may print a continuous segment of one character and later turns may overwrite the positions between them. The substring between k and j is handled separately by dp[k + 1][j - 1].

The algorithm tries every possible matching position k, so it considers every possible way for the final character s[j] to share a print turn with an earlier equal character.

Since substrings are processed by increasing length, all smaller intervals used in the recurrence are already computed.

Therefore, each dp[i][j] is optimal, and dp[0][n - 1] is the minimum number of turns needed to print the whole string.

Complexity

The official constraint is small enough for this interval DP approach: s.length <= 100.

Implementation

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                dp[i][j] = dp[i][j - 1] + 1

                for k in range(i, j):
                    if s[k] == s[j]:
                        middle = 0
                        if k + 1 <= j - 1:
                            middle = dp[k + 1][j - 1]

                        dp[i][j] = min(
                            dp[i][j],
                            dp[i][k] + middle,
                        )

        return dp[0][n - 1]

Code Explanation

We create a square DP table:

dp = [[0] * n for _ in range(n)]

Then initialize every one-character interval:

for i in range(n):
    dp[i][i] = 1

A single character always takes one turn.

We process intervals by length:

for length in range(2, n + 1):

For each interval, compute its right endpoint:

j = i + length - 1

The default choice is to print the final character separately:

dp[i][j] = dp[i][j - 1] + 1

Then we look for an earlier equal character:

for k in range(i, j):
    if s[k] == s[j]:

If s[k] == s[j], the character at j can share the same printing turn as the character at k.

The middle interval may be empty:

middle = 0
if k + 1 <= j - 1:
    middle = dp[k + 1][j - 1]

Then we update the best answer:

dp[i][j] = min(
    dp[i][j],
    dp[i][k] + middle,
)

Finally:

return dp[0][n - 1]

returns the minimum number of turns for the whole string.

Testing

def run_tests():
    s = Solution()

    assert s.strangePrinter("aaabbb") == 2
    assert s.strangePrinter("aba") == 2
    assert s.strangePrinter("abc") == 3
    assert s.strangePrinter("aaa") == 1
    assert s.strangePrinter("abab") == 3
    assert s.strangePrinter("abaaba") == 3

    print("all tests passed")

run_tests()

Test meaning: