Input: s ="aaabbb"Output: 2Explanation: Print "aaa" first and then print "bbb".
Example 2:
1
2
3
Input: s ="aba"Output: 2Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
This problem is similar to “Remove boxes” problem. We will try to club identical characters so that printing them all together will minimize the total number of operations. More:Remove Boxes
Take the example input: “aba”. If we take out ‘b’ from the input string, the remaining string will be “aa” which can be printed in one operation. One thing is left is ‘b’ which can be printed by replace operation. So when taking ‘b’ out, print ‘a’ instead and later replace it with ‘b’.
Try every possible way to print the string by grouping identical characters together. At each step, print a block of identical characters, then recursively solve the remaining string. The goal is to minimize the total number of print operations.
Start from index 0, pick the longest block of identical characters, print it, and recursively solve the rest. For each possible block, try both printing and replacing, and choose the minimum among all options. This explores all possible ways to group and print the string.
See the diagram below for more understanding.
---
title: s = aba
---
graph TD
A["aba"]
A -->|Operation 1: Print 'a' cost: 1| B["remaining: ba"]
A -->|Take out 'b', print 'a' cost: 1| C["remaining: nothing (print 'b' later)"]
A -->|Operation 1: Print 'a' cost: 1| D["remaining: ab"]
B -->|Operation 2: Print 'b' cost: 1| E["remaining: a"]
B -->|Take out 'a', print 'b' cost: 1| F["remaining: nothing (print 'a' later)"]
C -->|Operation 2: Print 'b' cost: 1| G["DONE: aba total cost: 2"]
D -->|Operation 2: Print 'a' cost: 1| H["remaining: b"]
D -->|Operation 2: Print 'b' cost: 1| I["remaining: a"]
E -->|Operation 3: Print 'a' cost: 1| J["DONE: aba total cost: 3"]
F -->|Operation 3: Print 'a' cost: 1| K["DONE: aba total cost: 3"]
H -->|Operation 3: Print 'b' cost: 1| L["DONE: aba total cost: 3"]
I -->|Operation 3: Print 'a' cost: 1| M["DONE: aba total cost: 3"]
G --> N5["return 2"]
J --> N1["return 3"]
K --> N2["return 3"]
L --> N3["return 3"]
M --> N4["return 3"]
N1 --> O1["E: 3"]
N2 --> O2["F: 3"]
N5 --> O5["C: 2 ⭐"]
N3 --> O3["H: 3"]
N4 --> O4["I: 3"]
O1 --> P1["B: min(3,3) = 3"]
O2 --> P1
O5 --> P2["Path 2: 2"]
O3 --> P3["D: min(3,3) = 3"]
O4 --> P3
P1 --> Final["A: min(3,2,3) = 2"]
P2 --> Final
P3 --> Final
classDef optimal fill:#9f9,stroke:#333,stroke-width:3px;
classDef calculation fill:#dff,stroke:#333,stroke-width:1px;
classDef done fill:#ffe,stroke:#333,stroke-width:2px;
class C,G,N5,O5,P2 optimal;
class N1,N2,N3,N4,N5,O1,O2,O3,O4,O5,P1,P2,P3 calculation;
class G,J,K,L,M done;
Explanation:
Path 1: Print ‘a’ first (1 op) → leaves “ba” → needs 2 more operations → total 3
Path 2: Take out ‘b’, print ‘a’ everywhere (1 op) → then print ‘b’ (1 op) → total 2 ⭐
Path 3: Print ‘a’ at end (1 op) → leaves “ab” → needs 2 more operations → total 3
The optimal strategy: Print ‘a’ across the entire string (1 op), then overwrite the middle position with ‘b’ (1 op) = 2 total operations
The recursive approach solves many subproblems repeatedly. By using memoization (top-down DP), we store results for each substring so that we never recompute the same subproblem twice. This drastically reduces the number of recursive calls.
Use a hash map (or language equivalent) to cache the minimum operations for each substring. Before making a recursive call, check if the result is already computed. If so, use it; otherwise, compute and store it. This is a classic top-down DP with memoization.
⏰ Time complexity: O(n^n) in the worst case, but much faster in practice due to memoization.
🧺 Space complexity: O(n^2) for the memoization table.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
### Method 3 - BU DP
#### Intuition
The top-down DP with memoization is efficient, but we can do even better by converting it to bottom-up tabulation. We build a DP tablewhere`dp[i][j]`is the minimum turns needed to print the substring fromindex`i`to`j`. We fill the table iteratively, considering all possible splits and merges of identical characters.
#### Approach
Initialize a 2D DP table. Foreach substring, try all possible splits and merge operations, updating the minimum turns needed. If the characters at the split point and the end are the same, we can merge the operations and save a turn.
#### Code
classSolution {
public:int strangePrinter(string s) {
int n = s.length();
if (n ==0) return0;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i =0; i < n; ++i) dp[i][i] =1;
for (int len =1; len < n; ++len) {
for (int i =0; i + len < n; ++i) {
int j = i + len;
dp[i][j] = len +1;
for (int k = i; k < j; ++k) {
int temp = dp[i][k] + dp[k+1][j];
if (s[k] == s[j]) temp--;
dp[i][j] = min(dp[i][j], temp);
}
}
}
return dp[0][n-1];
}
};
classSolution {
funstrangePrinter(s: String): Int {
val n = s.length
if (n ==0) return0val dp = Array(n) { IntArray(n) }
for (i in0 until n) dp[i][i] = 1for (len in1 until n) {
for (i in0 until n - len) {
val j = i + len
dp[i][j] = len + 1for (k in i until j) {
var temp = dp[i][k] + dp[k+1][j]
if (s[k] == s[j]) temp-- dp[i][j] = minOf(dp[i][j], temp)
}
}
}
return dp[0][n-1]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
defstrangePrinter(self, s: str) -> int:
n = len(s)
if n ==0:
return0 dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] =1for l in range(1, n):
for i in range(n-l):
j = i + l
dp[i][j] = l +1for k in range(i, j):
temp = dp[i][k] + dp[k+1][j]
if s[k] == s[j]:
temp -=1 dp[i][j] = min(dp[i][j], temp)
return dp[0][n-1]
impl Solution {
pubfnstrange_printer(s: String) -> i32 {
let n = s.len();
if n ==0 { return0; }
let bytes = s.as_bytes();
letmut dp =vec![vec![0; n]; n];
for i in0..n { dp[i][i] =1; }
for l in1..n {
for i in0..n-l {
let j = i + l;
dp[i][j] = l asi32+1;
for k in i..j {
letmut temp = dp[i][k] + dp[k+1][j];
if bytes[k] == bytes[j] { temp -=1; }
dp[i][j] = dp[i][j].min(temp);
}
}
}
dp[0][n-1]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
functionstrangePrinter(s: string):number {
constn=s.length;
if (n===0) return0;
constdp: number[][] = Array.from({length: n}, () => Array(n).fill(0));
for (leti=0; i<n; i++) dp[i][i] =1;
for (letl=1; l<n; l++) {
for (leti=0; i+l<n; i++) {
constj=i+l;
dp[i][j] =l+1;
for (letk=i; k<j; k++) {
lettemp=dp[i][k] +dp[k+1][j];
if (s[k] ===s[j]) temp--;
dp[i][j] = Math.min(dp[i][j], temp);
}
}
}
returndp[0][n-1];
}
#### Complexity
-⏰Time complexity: `O(n^3)`, where`n`is the length of the string. Three nested loops.
-🧺 Space complexity: `O(n^2)`, for the DP table.