664. Strange Printer

Intuition

The problem involves finding the minimum number of turns the strange printer needs to print the entire string s. The printer can only print a contiguous substring of the same character in one turn. Therefore, the key idea is to divide the problem into subproblems by considering the leftmost character as the start of the printing process and checking possible segments where we can split the string.

Approach

1. Recursive DP Approach:
2. Define a recursive function minCount(left, right) that returns the minimum number of turns needed to print the substring s[left:right+1].
3. If s[left] and s[i] are the same, we can minimize the number of turns by considering this segment as one part of the solution and applying the recursive function to the left and right parts of this segment.

4. Use memoization (memo[left][right]) to store already computed results for subproblems to avoid redundant calculations.

5. Base Case:

6. If left > right, return 0 because there’s nothing to print.

7. If memo[left][right] is already computed, return the stored value.

8. Recurrence Relation:

9. Start by assuming we need one more turn to print the substring from left to right.
10. Then, iterate through possible split points to minimize the number of turns by leveraging the already computed results from the recursive calls.

Complexity

• Time Complexity: The time complexity is O(n³) where n is the length of the string. This is because for each pair (left, right), the algorithm iterates over all possible splits, which takes O(n) time, and there are O(n²) subproblems.

• Space Complexity: The space complexity is O(n²) due to the memoization table used to store results for subproblems.

Code

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

public int strangePrinter(String s) {
    int N = s.length();
    this.s = s;
    this.memo = new int[N][N];
    return minCount(0, N - 1);
}

private int minCount(int left, int right) {
    if (left > right) {
        return 0;
    }
    if (memo[left][right] != 0) {
        return memo[left][right];
    }

    // Start with the assumption that we print s[left:right+1] as one color
    int best = minCount(left + 1, right) + 1;

    // Try to split the string at every possible index and find the minimum count
    for (int i = left + 1; i <= right; i++) {
        if (s.charAt(left) == s.charAt(i)) {
            best = Math.min(best, minCount(left, i - 1) + minCount(i + 1, right));
        }
    }
    memo[left][right] = best;
    return best;
}

}