664. Strange Printer

Problem Description

Imagine you have a printer, but it's quite peculiar because of two constraints:

It can only print a string of identical characters in one go.
You can print over already printed characters.

Now, with this printer, you're given a specific string s. The question asks us to find out the smallest number of turns or print operations to get the entire string s printed, considering the printer's constraints.

A “turn” or “print operation” is defined by the printer printing a sequence of the same character. So each time, you can choose a segment of your string and print a character across that segment, potentially covering up different characters that were there from previous turns.

For example, if your string "s" is "aaabbb", a possible print strategy could be:

In the first turn, print "aaa" from position 1 to 3.
In the second turn, print "bbb" from position 4 to 6. So you would need 2 turns to print "aaabbb".

The crux of the problem is to plan your print operations strategically to minimize the number of turns needed.

Intuition

To solve this problem, a dynamic programming (DP) approach is used. The intuition behind DP is to solve small problems and use their solutions to solve larger problems.

Firstly, we start by understanding that if the first and last characters to be printed are the same, we can deal with them in the same turn. If they aren't the same, we should consider splitting the problem into smaller segments and solving for those.

To implement this, we define a 2D array f, where f[i][j] represents the minimum number of operations needed to print the substring s[i..j].

The solution relies on a few key insights:

If s[i] == s[j] for some substring s[i..j], printing s[i] can include s[j] for free, reducing the number of operations.
When s[i] != s[j], we need to consider all possible places we can split the substring into two parts - s[i..k] and s[k+1..j]. We’re looking for the best place to split where the sum of operations for both substrings is minimized.
Since our solution to each substring depends on solutions to smaller substrings, we need to iterate from the end of the string to the beginning. This way, we ensure that the solution to any used substring is already computed.

So through a nested loop iterating over all possible substrings, and a third loop to handle splits within these substrings, we apply these insights and fill out the array f using the given relationship. The final answer will be in f[0][n-1], reflecting the minimum operations needed for the whole string s.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of the solution can be broken down as follows, based on the provided Reference Solution Approach:

Data Structures: We use a 2D array f of size n x n, where n is the length of the input string s. This array holds the sub-results for the number of operations required to print substrings of s. The default value for all positions in f is set to infinity (inf) because initially, we do not know the minimum operations to print any substring.
Initializing the 2D Array: We loop through the array f and initialize f[i][i] to 1 for all i, because printing a single character always requires exactly one operation.
Dynamic Programming: The core idea of dynamic programming is utilized here, where we solve for small substrings and use these solutions to solve for larger substrings. We iterate over the starting index i of the substring in reverse (from n-1 to 0) and the ending index j in the normal order (from i+1 to n-1).
Transitions and Recurrence Relation: The transition equations, as per the dynamic programming approach, are the cornerstone of this implementation.

If s[i] equals s[j], we leverage the insight that we can print the last character s[j] for 'free' when we print s[i], effectively ignoring s[j]. Therefore, f[i][j] = f[i][j - 1].
If s[i] is not equal to s[j], we consider all possibilities for splitting the substring into two parts. We iterate over every possible split point k between i and j-1. Our goal is to minimize the total print operations for the two substrings, so we calculate f[i][j] as the minimum of its current value and f[i][k] + f[k+1][j].

Answer Retrieval: After all iterations and updates to the 2D array f, the answer to the problem, which is the minimum number of operations needed to print the entire string, is stored in f[0][n-1].

In summary, the approach translates the problem into finding the minimal steps for progressively larger substrings using principles of dynamic programming. The solution carefully considers the two properties of the printer, especially the fact that a sequence of the same character can be used advantageously to reduce operation counts.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the string "abba" to illustrate the solution approach.

Data Structures: We create a 2D array f of size 4 x 4 since the string "abba" has 4 characters. We initialize all values to infinity except for f[i][i], which we set to 1 since a single character can always be printed in one operation.

Initial f array:

f[0][0] = 1    f[0][1] = inf    f[0][2] = inf    f[0][3] = inf
f[1][0] = ∅    f[1][1] = 1      f[1][2] = inf    f[1][3] = inf
f[2][0] = ∅    f[2][1] = ∅      f[2][2] = 1      f[2][3] = inf
f[3][0] = ∅    f[3][1] = ∅      f[3][2] = ∅      f[3][3] = 1

Initializing the 2D Array: We've already initialized f[i][i] to 1.
Dynamic Programming: We consider all substrings starting from length 2 to the full string length. For "abba", we consider "ab", "bb", and "ba" for lengths 2, and "abb" and "bba" for length 3, and finally "abba" for length 4.
Transitions and Recurrence Relation:

a. For "ab" (s[0] != s[1]), we split at every point (though there's only one in this case), and find that f[0][1] should be f[0][0] + f[1][1] which evaluates to 2.

b. For "bb" (s[1] == s[2]), the characters are the same, so f[1][2] is just f[1][1] which is 1.

c. For "ba" (s[1] != s[2]), similar to "ab", f[2][3] should be f[2][2] + f[3][3] giving us 2.

d. Now we look at "abb" and "bba":
- For "abb" (s[0] != s[2]), we check both splits "a | bb" and "ab | b" and we find the minimum of f[0][0] + f[1][2] and f[0][1] + f[2][2], which will be the minimum of 2 and 3, so f[0][2] becomes 2.
- For "bba" (s[1] != s[3]), we do a similar check and find f[1][3] to also be 2.
e. Finally, for "abba" (s[0] == s[3]), we either consider it as "a | bba" or "abb | a", or we take advantage of the fact that the first and last characters are the same. So we just need the result of "abb", which is 2.

Updated f array:
```
f[0][0] = 1    f[0][1] = 2    f[0][2] = 2    f[0][3] = 2
f[1][0] = ∅    f[1][1] = 1    f[1][2] = 1    f[1][3] = 2
f[2][0] = ∅    f[2][1] = ∅    f[2][2] = 1    f[2][3] = 2
f[3][0] = ∅    f[3][1] = ∅    f[3][2] = ∅    f[3][3] = 1
```
Answer Retrieval: The minimum number of operations needed to print the entire string "abba" is in f[0][3], which is 2.

As the example shows, the DP approach systematically reduces the complexity by utilizing the relationship between substrings, allowing us to find the minimum number of print operations needed.

Solution Implementation

1class Solution:
2    def strangePrinter(self, string: str) -> int:
3        # Length of the input string
4        length = len(string)
5        # Initialize the operations matrix with infinity, representing the minimum number of turns
6        operations = [[float('inf')] * length for _ in range(length)]
7      
8        # Start from the end of the string and move towards the beginning
9        for start in range(length - 1, -1, -1):
10            # A single character takes one turn to print
11            operations[start][start] = 1
12          
13            # Fill the operations matrix for substrings [start:end+1]
14            for end in range(start + 1, length):
15                # If the characters at the start and end are the same,
16                # it takes the same number of turns as [start:end-1]
17                if string[start] == string[end]:
18                    operations[start][end] = operations[start][end - 1]
19                else:
20                    # If they are different, find the minimum number of turns needed
21                    # to print the substring by splitting it at different points (k)
22                    for split_point in range(start, end):
23                        # The number of turns is the sum of printing both substrings separately
24                        operations[start][end] = min(
25                            operations[start][end],
26                            operations[start][split_point] + operations[split_point + 1][end]
27                        )
28      
29        # Return the minimum number of turns to print the whole string
30        return operations[0][-1]
31

1class Solution {
2    public int strangePrinter(String s) {
3        final int INFINITY = Integer.MAX_VALUE / 2; // value representing infinity, halved to avoid overflow when adding
4        int length = s.length(); // length of the input string
5        int[][] dp = new int[length][length]; // initialize DP table, dp[i][j] represents the minimal turns to print s[i..j]
6      
7        for (int[] row : dp) {
8            Arrays.fill(row, INFINITY); // fill the DP table with 'infinity' as initial value
9        }
10      
11        for (int i = length - 1; i >= 0; --i) { // iterate from the end to the beginning of the string
12            dp[i][i] = 1; // it takes 1 turn to print a single character
13          
14            for (int j = i + 1; j < length; ++j) { // iterate over the rest of the string
15                if (s.charAt(i) == s.charAt(j)) { // if characters match, it costs the same as without the last character
16                    dp[i][j] = dp[i][j - 1];
17                } else {
18                    for (int k = i; k < j; ++k) { // split the range into two parts and sum their costs
19                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]); // find the minimum cost
20                    }
21                }
22            }
23        }
24      
25        return dp[0][length - 1]; // answer is the minimal turns to print the entire string s[0..length-1]
26    }
27}
28

1class Solution {
2public:
3    int strangePrinter(string s) {
4        int length = s.size();
5        // Create a 2D array to store the minimum number of turns needed
6        // Initialize all entries with a high value (0x3f3f3f3f) to signify uncalculated/infinity
7        int dp[length][length];
8        memset(dp, 0x3f, sizeof(dp));
9
10        // Loop backwards through the string (start from the end)
11        for (int start = length - 1; start >= 0; --start) {
12            // Always takes one turn to print a single character
13            dp[start][start] = 1;
14
15            // Iterate over the substring from the current start to the end of the string
16            for (int end = start + 1; end < length; ++end) {
17                // If the characters are the same, it takes the same number of turns
18                // as it took to print the substring without the current character
19                // because it can be printed in the same turn as the last character
20                if (s[start] == s[end]) {
21                    dp[start][end] = dp[start][end - 1];
22                } else {
23                    // If characters are different, find the minimum number of turns
24                    // needed by splitting the substring into two parts at every possible position
25                    for (int split = start; split < end; ++split) {
26                        dp[start][end] = min(dp[start][end], dp[start][split] + dp[split + 1][end]);
27                    }
28                }
29            }
30        }
31
32        // The answer is the minimum number of turns to print the whole string
33        // which is stored in dp[0][length - 1]
34        return dp[0][length - 1];
35    }
36};
37

1function strangePrinter(s: string): number {
2    const length = s.length;
3    // Initialize a 2D array to store the minimum number of turns for [i..j] substring.
4    const dp: number[][] = new Array(length).fill(0).map(() => new Array(length).fill(Infinity));
5  
6    // Traverse the string in reverse to deal with substrings in a bottom-up manner.
7    for (let i = length - 1; i >= 0; --i) {
8        // A single character needs one turn to be printed.
9        dp[i][i] = 1;
10
11        // Compute the number of turns needed for substrings [i..j]
12        for (let j = i + 1; j < length; ++j) {
13            // If the characters at position i and j are the same,
14            // no extra turn is needed beyond what is required for [i..j-1]
15            if (s[i] === s[j]) {
16                dp[i][j] = dp[i][j - 1];
17            } else {
18                // If characters are different, find the split point 'k'
19                // that minimizes the sum of turns for [i..k] and [k+1..j] substrings.
20                for (let k = i; k < j; ++k) {
21                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
22                }
23            }
24        }
25    }
26  
27    // The result for the entire string is then stored in dp[0][length - 1].
28    return dp[0][length - 1];
29}
30

Time and Space Complexity

The time complexity of the code is O(n^3) due to the triple nested loop structure where n is the length of string s. The outer loop runs n times in reverse, the middle loop runs a maximum of n times for each value of i, and the inner loop, also running up to n times for each combination of i and j, represents the main source of the cubic time complexity. Inside the inner loop, the code checks every substring from i to j and calculates the minimum operations required by comparing the current value of f[i][j] with f[i][k] + f[k + 1][j], where k is between i and j-1.

The space complexity of the code is O(n^2) which is caused by the storage requirements of the 2D array f that has a size of n * n, necessary for dynamic programming and storing the minimum print operations for every substring from i to j.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don't know