Strange Printer

HARD

Description

There is a strange printer with the following two special properties:

The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string s, return the minimum number of turns the printer needed to print it.

Example 1:

Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

Example 2:

Input: s = "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.

Approaches

Checkout 2 different approaches to solve Strange Printer. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Recursion

This approach attempts to solve the problem by exploring all possible sequences of print operations in a recursive manner. For any given substring, it tries two main strategies: printing the first character by itself and then solving for the rest, or finding a matching character later in the string to form a combined print, which splits the problem into two subproblems. This method directly translates the problem's combinatorial nature into code.

Algorithm

Define a recursive function solve(s, i, j) that computes the minimum turns for the substring s[i...j].
Base Case: If i > j, the substring is empty, return 0. If i == j, the substring has one character, return 1.
Recursive Step:
1. Calculate a result by printing the first character s[i] alone and then solving for the rest of the string: res = 1 + solve(s, i + 1, j).
2. Iterate with a variable k from i + 1 to j. If s.charAt(k) is the same as s.charAt(i), it means we can potentially use one print operation for both. This splits the problem into two independent subproblems: s[i+1...k-1] and s[k...j]. The cost for this strategy is solve(s, i + 1, k - 1) + solve(s, k, j).
3. Update res to be the minimum of its current value and the value from the split.
Return the final res.
The initial call would be solve(s, 0, s.length() - 1).

The brute-force recursive solution defines a function, let's call it solve(i, j), that calculates the minimum turns needed to print the substring s[i...j]. The base cases for the recursion are simple: an empty substring (i > j) requires 0 turns, and a single-character substring (i == j) requires 1 turn.

For a general substring s[i...j], the function explores all valid moves. A default move is to print the character s[i] in a single turn and then recursively solve for the remaining substring s[i+1...j]. The cost of this move is 1 + solve(i+1, j).

To optimize, the function looks for any character s[k] (where k is between i+1 and j) that is identical to s[i]. If such a character is found, it represents an opportunity to use a single print operation to cover both s[i] and s[k]. This splits the problem into solving for the parts in between (s[i+1...k-1]) and the part after (s[k...j]). The cost would be the sum of the solutions to these subproblems. The function calculates the minimum cost among all these possibilities.

Since this method re-computes solutions for the same substrings repeatedly, its performance is very poor.

Complexity Analysis

Time Complexity: Exponential, likely in the order of O(2^N * N). For each subproblem, we might branch multiple times, leading to an explosion in the number of calls.Space Complexity: O(N), where N is the length of the string. This space is used by the recursion call stack.

Pros and Cons

Pros:

Simple to understand and implement as it directly models the recursive structure of the problem.

Cons:

Extremely inefficient due to a massive number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for constraints of N > 15-20.

Code Solutions

Checking out 3 solutions in different languages for Strange Printer. Click on different languages to view the code.

class Solution { public int strangePrinter ( String s ) { final int inf = 1 << 30 ; int n = s . length (); int [][] f = new int [ n ][ n ]; for ( var g : f ) { Arrays . fill ( g , inf ); } for ( int i = n - 1 ; i >= 0 ; -- i ) { f [ i ][ i ] = 1 ; for ( int j = i + 1 ; j < n ; ++ j ) { if ( s . charAt ( i ) == s . charAt ( j )) { f [ i ][ j ] = f [ i ][ j - 1 ]; } else { for ( int k = i ; k < j ; ++ k ) { f [ i ][ j ] = Math . min ( f [ i ][ j ], f [ i ][ k ] + f [ k + 1 ][ j ]); } } } } return f [ 0 ][ n - 1 ]; } }

Video Solution

Watch the video walkthrough for Strange Printer

Patterns:

Dynamic Programming

Data Structures:

String

Companies:

Cisco |NetEase |