We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Strange Printer

Number: 664

Difficulty: Hard

Paid? No

Companies: Bloomberg, Google, Cisco, Amazon, Uber, NetEase

Problem Description

Given a string s, determine the minimum number of turns required by a strange printer to print it. The printer can only print a sequence of the same character each time, and each turn can paint a contiguous segment—overwriting existing characters if necessary.

Key Insights

  • Use dynamic programming where dp[i][j] represents the minimum turns needed to print the substring s[i...j].
  • Base case: dp[i][i] = 1, since a single character takes one turn.
  • If s[i] and s[j] are the same, the last print can cover both, potentially reducing the turn count.
  • For every substring, try all possible partitions and combine results, taking advantage of matching characters to merge operations.

Space and Time Complexity

Time Complexity: O(n^3) in the worst case because of three nested loops to fill in the dp table. Space Complexity: O(n^2) due to the dp table storing solutions for each substring.

Solution

We use a 2D dynamic programming table dp where dp[i][j] indicates the minimum turns needed to print substring s[i...j]. Initialize dp[i][i] = 1 for all i. For each substring of length >=2, set dp[i][j] = dp[i][j-1] + 1 by default (printing s[j] separately). Then, iterate through every index k from i to j - 1; if s[k] equals s[j], merge the operation by calculating dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1]) while handling edge cases. This approach systematically breaks down the problem into smaller overlapping subproblems.

Code Solutions

# Python solution for Strange Printer

def strangePrinter(s: str) -> int:
    n = len(s)
    # Initialize a 2D dp table with zeros.
    dp = [[0] * n for _ in range(n)]
    
    # Base case: each single character requires 1 turn.
    for i in range(n):
        dp[i][i] = 1

    # Process all substrings of increasing lengths.
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Assume printing s[j] separately after s[i...j-1].
            dp[i][j] = dp[i][j - 1] + 1
            # Try merging operations where s[k] equals s[j].
            for k in range(i, j):
                if s[k] == s[j]:
                    # When merging, cost is dp[i][k] plus dp[k+1][j-1], if any.
                    cost = dp[i][k] + (dp[k + 1][j - 1] if k + 1 <= j - 1 else 0)
                    dp[i][j] = min(dp[i][j], cost)
    return dp[0][n - 1]

# Example usage:
s = "aba"
print(strangePrinter(s))  # Output: 2
← Back to All Questions