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 sizen x n
, wheren
is the length of the input strings
. This array holds the sub-results for the number of operations required to print substrings ofs
. The default value for all positions inf
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 initializef[i][i]
to1
for alli
, 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 (fromn-1
to0
) and the ending indexj
in the normal order (fromi+1
ton-1
). -
Transitions and Recurrence Relation: The transition equations, as per the dynamic programming approach, are the cornerstone of this implementation.
- If
s[i]
equalss[j]
, we leverage the insight that we can print the last characters[j]
for 'free' when we prints[i]
, effectively ignorings[j]
. Therefore,f[i][j] = f[i][j - 1]
. - If
s[i]
is not equal tos[j]
, we consider all possibilities for splitting the substring into two parts. We iterate over every possible split pointk
betweeni
andj-1
. Our goal is to minimize the total print operations for the two substrings, so we calculatef[i][j]
as the minimum of its current value andf[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 inf[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 EvaluatorExample Walkthrough
Let's use the string "abba" to illustrate the solution approach.
-
Data Structures: We create a 2D array
f
of size4 x 4
since the string "abba" has 4 characters. We initialize all values to infinity except forf[i][i]
, which we set to1
since a single character can always be printed in one operation.Initial
f
array:1f[0][0] = 1 f[0][1] = inf f[0][2] = inf f[0][3] = inf 2f[1][0] = ∅ f[1][1] = 1 f[1][2] = inf f[1][3] = inf 3f[2][0] = ∅ f[2][1] = ∅ f[2][2] = 1 f[2][3] = inf 4f[3][0] = ∅ f[3][1] = ∅ f[3][2] = ∅ f[3][3] = 1
-
Initializing the 2D Array: We've already initialized
f[i][i]
to1
. -
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 thatf[0][1]
should bef[0][0]
+f[1][1]
which evaluates to2
.b. For "bb" (
s[1]
==s[2]
), the characters are the same, sof[1][2]
is justf[1][1]
which is1
.c. For "ba" (
s[1]
!=s[2]
), similar to "ab",f[2][3]
should bef[2][2]
+f[3][3]
giving us2
.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 off[0][0] + f[1][2]
andf[0][1] + f[2][2]
, which will be the minimum of2
and3
, sof[0][2]
becomes2
. - For "bba" (
s[1]
!=s[3]
), we do a similar check and findf[1][3]
to also be2
.
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 is2
.Updated
f
array:1f[0][0] = 1 f[0][1] = 2 f[0][2] = 2 f[0][3] = 2 2f[1][0] = ∅ f[1][1] = 1 f[1][2] = 1 f[1][3] = 2 3f[2][0] = ∅ f[2][1] = ∅ f[2][2] = 1 f[2][3] = 2 4f[3][0] = ∅ f[3][1] = ∅ f[3][2] = ∅ f[3][3] = 1
- For "abb" (
-
Answer Retrieval: The minimum number of operations needed to print the entire string "abba" is in
f[0][3]
, which is2
.
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.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Submit the part you don't understand to our editors. Or join our Discord and ask the community.