# Strange Printer
**Difficulty:** HARD
[External](https://leetcode.com/problems/strange-printer)
Canonical: https://scaleengineer.com/dsa/problems/strange-printer
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [NetEase](https://scaleengineer.com/companies/netease)
---
## Problem
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
## 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.
**Time:** 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:** O(N), where N is the length of the string. This space is used by the recursion call stack.
**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.
### Explanation
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.
### 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)`.

## Dynamic Programming with Memoization
This is the standard and efficient approach for this problem, utilizing dynamic programming with memoization (a top-down DP approach). It improves upon the brute-force method by storing the results of subproblems in a 2D array, thereby avoiding redundant calculations. Before starting, the input string is compressed by removing consecutive duplicates (e.g., "aaabbb" becomes "ab"), which reduces the problem size without affecting the answer.
**Time:** O(N^3), where N is the length of the (potentially compressed) string. There are O(N^2) states (subproblems), and each state takes O(N) time to compute due to the inner loop that searches for matching characters. · **Space:** O(N^2), where N is the length of the (potentially compressed) string. This space is required for the memoization table.
**Pros:** Efficient enough to solve the problem within typical time limits due to the O(N^3) complexity.; Guaranteed to find the optimal solution.; The preprocessing step of compressing the string is a simple and effective optimization.
**Cons:** The O(N^3) time complexity might be too slow if the constraints on N were significantly larger.; The recurrence relation's logic can be non-trivial to derive and prove correct.
### Explanation
The core of this approach is a recursive function that computes the minimum turns for a substring `s[i...j]`, but with a cache (memoization table) to store results. This prevents re-solving the same subproblem multiple times.

First, we preprocess the string. For instance, `s = "aaabbb"` becomes `"ab"`. The minimum turns for both are the same. Let's call the new string `s_prime`.

We define a function `solve(i, j)` and a 2D array `memo`. `memo[i][j]` will store the result for `s_prime[i...j]`.

The recurrence relation is as follows:
1.  A baseline strategy is to print `s_prime[i]` in one turn and then solve for the rest, `s_prime[i+1...j]`. This gives `1 + solve(i+1, j)` turns.
2.  We can do better if there's another character `s_prime[k]` (for `k > i`) that matches `s_prime[i]`. If so, we can use a single print operation for `s_prime[i]` that also covers the character at position `k`. This effectively merges the problem of printing `s_prime[i...k-1]` with `s_prime[k...j]`. The cost of this combined operation is `solve(i+1, k-1) + solve(k, j)`. The intuition is that the turn printing `s_prime[i]` can be the same turn that starts printing the subproblem `s_prime[k...j]`, saving one operation.

We take the minimum over all these possibilities. The result for each `(i, j)` pair is stored in `memo[i][j]` to be reused.

```java
class Solution {
    private int[][] memo;
    private String s;

    public int strangePrinter(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // Compress the string
        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                sb.append(s.charAt(i));
            }
        }
        this.s = sb.toString();
        int n = this.s.length();
        this.memo = new int[n][n];
        
        return solve(0, n - 1);
    }

    private int solve(int i, int j) {
        if (i > j) {
            return 0;
        }
        if (i == j) {
            return 1;
        }
        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        // Option 1: Print s[i] and solve for the rest
        int res = 1 + solve(i + 1, j);

        // Option 2: Find s[k] == s[i] and merge operations
        for (int k = i + 1; k <= j; k++) {
            if (s.charAt(k) == s.charAt(i)) {
                res = Math.min(res, solve(i + 1, k - 1) + solve(k, j));
            }
        }

        return memo[i][j] = res;
    }
}
```
An iterative, bottom-up DP solution can also be implemented with the same time and space complexity.
### Algorithm
*   First, preprocess the input string `s` to remove any consecutive duplicate characters. This is a safe optimization because printing 'aaa' is the same as printing 'a' in terms of turn count. Let the compressed string be `s_prime` of length `n`.
*   Create a 2D array `memo[n][n]` to store the results of subproblems, initialized to a value indicating 'not computed' (e.g., 0).
*   Define a recursive helper function `solve(i, j)`:
    *   **Base Cases:** If `i > j`, return 0. If `i == j`, return 1.
    *   **Memoization Check:** If `memo[i][j]` has been computed, return the stored value.
    *   **Recursive Calculation:**
        1.  Initialize the result for `s_prime[i...j]` with a safe upper bound: `res = 1 + solve(i + 1, j)`. This corresponds to printing `s_prime[i]` and then solving for the rest.
        2.  Iterate `k` from `i + 1` to `j`. If `s_prime.charAt(k) == s_prime.charAt(i)`, we have an opportunity to merge operations. Update the result: `res = min(res, solve(i + 1, k - 1) + solve(k, j))`.
    *   Store the final `res` in `memo[i][j]` and return it.
*   The main function calls `solve(0, n - 1)` to get the result for the entire compressed string.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

```cpp
class Solution { public: int strangePrinter ( string s ) { int n = s . size (); int f [ n ][ n ]; memset ( f , 0x3f , sizeof ( f )); for ( int i = n - 1 ; ~ i ; -- i ) { f [ i ][ i ] = 1 ; for ( int j = i + 1 ; j < n ; ++ j ) { if ( s [ i ] == s [ j ]) { f [ i ][ j ] = f [ i ][ j - 1 ]; } else { for ( int k = i ; k < j ; ++ k ) { f [ i ][ j ] = min ( f [ i ][ j ], f [ i ][ k ] + f [ k + 1 ][ j ]); } } } } return f [ 0 ][ n - 1 ]; } };
```

### Python

```python
class Solution : def strangePrinter ( self , s : str ) -> int : n = len ( s ) f = [[ inf ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): f [ i ][ i ] = 1 for j in range ( i + 1 , n ): if s [ i ] == s [ j ]: f [ i ][ j ] = f [ i ][ j - 1 ] else : for k in range ( i , j ): f [ i ][ j ] = min ( f [ i ][ j ], f [ i ][ k ] + f [ k + 1 ][ j ]) return f [ 0 ][ - 1 ]
```