LeetCode 664 - Strange Printer

The problem describes a "strange printer" that can print sequences of the same character in one turn. The printer can overwrite any existing characters in the string.

leetcodehardstringdynamic-programming

LeetCode Problem 664

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem describes a "strange printer" that can print sequences of the same character in one turn. The printer can overwrite any existing characters in the string. Given an input string s, the goal is to determine the minimum number of printing operations required to print the entire string.

In other words, we want to find the least number of contiguous character sequences needed to reproduce the string using this printer. The input is a string of lowercase English letters, with a length between 1 and 100. The constraints imply that a brute-force solution might be feasible for very small strings, but for lengths approaching 100, we need a more optimized approach.

Edge cases include:

  1. Strings with all identical characters, e.g., "aaaa". Only one turn is needed.
  2. Strings with alternating characters, e.g., "abab". Each different character might require careful overlap planning.
  3. Strings of length 1, e.g., "a". Only one turn is needed.

The problem guarantees a non-empty string, so we do not need to handle empty input.

Approaches

Brute Force Approach:

A naive brute-force method would consider printing every possible substring in every possible order. At each step, the algorithm could try printing a substring of identical characters and recursively calculate the minimum turns needed for the remaining string. While this approach is correct in principle, it is exponentially slow because the number of ways to partition the string grows extremely fast with length. It cannot handle strings of length up to 100.

Optimized Approach:

The key insight is that dynamic programming can reduce the complexity by exploiting overlapping subproblems. Let dp[i][j] be the minimum number of turns needed to print the substring s[i..j].

If s[i] == s[j], the last character s[j] can be printed in the same turn as s[i], reducing the required number of turns. Otherwise, we consider splitting the substring at every possible index k between i and j and take the minimum sum of dp[i][k] + dp[k+1][j]. This avoids redundant calculations and ensures the optimal solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n^2) Tries all partitions and printing orders, too slow for n=100
Optimal O(n^3) O(n^2) Uses DP to store subproblem results and splits substrings efficiently

Algorithm Walkthrough

  1. Initialize a 2D DP array dp of size n x n, where n is the length of the string. dp[i][j] will store the minimum number of turns needed to print substring s[i..j].
  2. For substrings of length 1 (i.e., i == j), set dp[i][i] = 1 because a single character only requires one turn.
  3. Iterate over substring lengths from 2 to n.
  4. For each substring length, iterate over all starting indices i to compute the ending index j = i + length - 1.
  5. Initialize dp[i][j] to dp[i][j-1] + 1, which represents printing s[j] in a new turn after printing s[i..j-1].
  6. Iterate over all k from i to j-1. If s[k] == s[j], consider merging turns: update dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1]).
  7. Return dp[0][n-1] as the minimum number of turns to print the entire string.

Why it works:

The algorithm works because the DP table correctly represents the minimum turns needed for every substring. By splitting substrings at all possible points and merging turns when characters match, it ensures no optimal solution is missed.

Python Solution

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        
        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]:
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1])
        
        return dp[0][n-1]

The DP array is initialized to store the minimum number of turns for each substring. Single characters require one turn. For longer substrings, we consider printing the last character separately or merging with previous characters if they match. The solution iteratively builds up the DP table, ensuring all substrings are considered.

Go Solution

func strangePrinter(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }
    
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }
    
    for length := 2; length <= n; length++ {
        for i := 0; i <= n - length; i++ {
            j := i + length - 1
            dp[i][j] = dp[i][j-1] + 1
            for k := i; k < j; k++ {
                if s[k] == s[j] {
                    if k+1 <= j-1 {
                        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j-1])
                    } else {
                        dp[i][j] = min(dp[i][j], dp[i][k])
                    }
                }
            }
        }
    }
    
    return dp[0][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Go requires explicit slice initialization for the 2D array. The main logic is identical to Python, but care is taken to handle index boundaries when k+1 > j-1.

Worked Examples

Example 1: "aaabbb"

i j dp[i][j] Explanation
0 0 1 Single 'a'
0 1 1 'aa' can be printed in one turn
0 2 1 'aaa' in one turn
3 3 1 Single 'b'
3 4 1 'bb' in one turn
3 5 1 'bbb' in one turn
0 5 2 Print 'aaa' then 'bbb'

Example 2: "aba"

i j dp[i][j] Explanation
0 0 1 'a'
1 1 1 'b'
2 2 1 'a'
0 1 2 'ab' requires 2 turns
1 2 2 'ba' requires 2 turns
0 2 2 Merge first and last 'a', print 'aaa' then 'b'

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) Three nested loops: length, start index, split index
Space O(n^2) 2D DP table storing all substring results

The cubic time arises from considering all substring lengths and all split points. The quadratic space is needed to store results for every substring.

Test Cases

# Provided examples
assert Solution().strangePrinter("aaabbb") == 2  # consecutive blocks
assert Solution().strangePrinter("aba") == 2     # alternating characters

# Single character
assert Solution().strangePrinter("a") == 1       # minimum input size

# All same character
assert Solution().strangePrinter("aaaaa") == 1   # all characters same

# Alternating characters
assert Solution().strangePrinter("ababab") == 3  # requires careful merging

# Longer repeated blocks
assert Solution().strangePrinter("abcabc") == 5  # multiple merges needed

# Edge case: length 2
assert Solution().strangePrinter("ab") == 2      # minimal alternating
Test Why
"aaabbb" Tests consecutive blocks of same characters
"aba" Tests alternating characters requiring merging
"a" Minimum input size
"aaaaa" All characters same, only one turn
"ababab" Alternating pattern, tests DP merging
"abcabc" Multiple