Strange Printer

• 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.

• 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.

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.

1class Solution {2    private int[][] memo;3    private String s;4 5    public int strangePrinter(String s) {6        if (s == null || s.length() == 0) {7            return 0;8        }9 10        // Compress the string11        StringBuilder sb = new StringBuilder();12        sb.append(s.charAt(0));13        for (int i = 1; i < s.length(); i++) {14            if (s.charAt(i) != s.charAt(i - 1)) {15                sb.append(s.charAt(i));16            }17        }18        this.s = sb.toString();19        int n = this.s.length();20        this.memo = new int[n][n];21        22        return solve(0, n - 1);23    }24 25    private int solve(int i, int j) {26        if (i > j) {27            return 0;28        }29        if (i == j) {30            return 1;31        }32        if (memo[i][j] != 0) {33            return memo[i][j];34        }35 36        // Option 1: Print s[i] and solve for the rest37        int res = 1 + solve(i + 1, j);38 39        // Option 2: Find s[k] == s[i] and merge operations40        for (int k = i + 1; k <= j; k++) {41            if (s.charAt(k) == s.charAt(i)) {42                res = Math.min(res, solve(i + 1, k - 1) + solve(k, j));43            }44        }45 46        return memo[i][j] = res;47    }48}

An iterative, bottom-up DP solution can also be implemented with the same time and space complexity.