Problem

There is a strange printer with the following two special properties:

  • The printer can only print a sequence of the same character each time.
  • At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string s, return the minimum number of turns the printer needed to print it.

Examples

Example 1:

1
2
3
Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

Example 2:

1
2
3
Input: s = "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

Solution

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

Method 1 - Recursion

Intuition

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.

Approach

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
	int strangePrinter(string s) {
		function<int(string)> dfs = [&](string input) {
			int operations = input.length();
			if (input.empty()) return 0;
			if (input.length() == 1) return 1;
			int start = 0, end = 0, n = input.length();
			while (start < n) {
				char c = input[start];
				while (end < n && input[end] == c) end++;
				if (end >= n)
					operations = min(operations, dfs(input.substr(0, start)) + 1);
				else
					operations = min(operations, dfs(input.substr(0, start) + input.substr(end)) + 1);
				start = end;
			}
			return operations;
		};
		return dfs(s);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func strangePrinter(s string) int {
	var dfs func(string) int
	dfs = func(input string) int {
		operations := len(input)
		if len(input) == 0 {
			return 0
		}
		if len(input) == 1 {
			return 1
		}
		start, end := 0, 0
		n := len(input)
		for start < n {
			c := input[start]
			for end < n && input[end] == c {
				end++
			}
			if end >= n {
				operations = min(operations, dfs(input[:start])+1)
			} else {
				operations = min(operations, dfs(input[:start]+input[end:])+1)
			}
			start = end
		}
		return operations
	}
	return dfs(s)
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public int strangePrinter(String input) {
	int operations = input.length();
	if (input == null || input.length() == 0) return 0;
	int size = input.length();
	if (size == 1) return 1;
	int start = 0, end = 0;
	while (start < size) {
		char c = input.charAt(start);
		while (end < size && c == input.charAt(end)) end++;
		if (end >= size) {
			operations = Math.min(operations, strangePrinter(input.substring(0, start)) + 1);
		} else {
			operations = Math.min(operations, strangePrinter(input.substring(0, start) + input.substring(end)) + 1);
		}
		start = end;
	}
	return operations;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
	fun strangePrinter(s: String): Int {
		fun dfs(input: String): Int {
			var operations = input.length
			if (input.isEmpty()) return 0
			if (input.length == 1) return 1
			var start = 0
			var end = 0
			val n = input.length
			while (start < n) {
				val c = input[start]
				while (end < n && input[end] == c) end++
				if (end >= n)
					operations = minOf(operations, dfs(input.substring(0, start)) + 1)
				else
					operations = minOf(operations, dfs(input.substring(0, start) + input.substring(end)) + 1)
				start = end
			}
			return operations
		}
		return dfs(s)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	def strangePrinter(self, s: str) -> int:
		def dfs(input: str) -> int:
			operations = len(input)
			if not input:
				return 0
			if len(input) == 1:
				return 1
			start, end = 0, 0
			n = len(input)
			while start < n:
				c = input[start]
				while end < n and input[end] == c:
					end += 1
				if end >= n:
					operations = min(operations, dfs(input[:start]) + 1)
				else:
					operations = min(operations, dfs(input[:start] + input[end:]) + 1)
				start = end
			return operations
		return dfs(s)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
impl Solution {
	pub fn strange_printer(s: String) -> i32 {
		fn dfs(input: &str) -> i32 {
			let mut operations = input.len() as i32;
			if input.is_empty() { return 0; }
			if input.len() == 1 { return 1; }
			let n = input.len();
			let bytes = input.as_bytes();
			let mut start = 0;
			while start < n {
				let c = bytes[start];
				let mut end = start;
				while end < n && bytes[end] == c { end += 1; }
				if end >= n {
					operations = operations.min(dfs(&input[..start]) + 1);
				} else {
					operations = operations.min(dfs(&[&input[..start], &input[end..]].concat()) + 1);
				}
				start = end;
			}
			operations
		}
		dfs(&s)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function strangePrinter(s: string): number {
	function dfs(input: string): number {
		let operations = input.length;
		if (!input) return 0;
		if (input.length === 1) return 1;
		let start = 0, end = 0, n = input.length;
		while (start < n) {
			const c = input[start];
			while (end < n && input[end] === c) end++;
			if (end >= n)
				operations = Math.min(operations, dfs(input.slice(0, start)) + 1);
			else
				operations = Math.min(operations, dfs(input.slice(0, start) + input.slice(end)) + 1);
			start = end;
		}
		return operations;
	}
	return dfs(s);
}

Complexity

  • ⏰ Time complexity: O(n^n) in the worst case, as every substring can be split in many ways.
  • 🧺 Space complexity: O(n) for the recursion stack.

Method 2 - Dynamic Programming

Intuition

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.

Approach

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.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
	unordered_map<string, int> memo;
	int strangePrinter(string s) {
		function<int(string)> dfs = [&](string input) {
			if (input.empty()) return 0;
			if (input.length() == 1) return 1;
			if (memo.count(input)) return memo[input];
			int operations = input.length();
			int start = 0, end = 0, n = input.length();
			while (start < n) {
				char c = input[start];
				while (end < n && input[end] == c) end++;
				if (end >= n)
					operations = min(operations, dfs(input.substr(0, start)) + 1);
				else
					operations = min(operations, dfs(input.substr(0, start) + input.substr(end)) + 1);
				start = end;
			}
			memo[input] = operations;
			return operations;
		};
		return dfs(s);
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func strangePrinter(s string) int {
	memo := make(map[string]int)
	var dfs func(string) int
	dfs = func(input string) int {
		if len(input) == 0 {
			return 0
		}
		if len(input) == 1 {
			return 1
		}
		if v, ok := memo[input]; ok {
			return v
		}
		operations := len(input)
		start, end := 0, 0
		n := len(input)
		for start < n {
			c := input[start]
			for end < n && input[end] == c {
				end++
			}
			if end >= n {
				operations = min(operations, dfs(input[:start])+1)
			} else {
				operations = min(operations, dfs(input[:start]+input[end:])+1)
			}
			start = end
		}
		memo[input] = operations
		return operations
	}
	return dfs(s)
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
HashMap<String,Integer> map = new HashMap<>();
public int strangePrinter(String input) {
	int operations = input.length();
	if (input == null || input.length() == 0) return 0;
	if (map.containsKey(input)) return map.get(input);
	int size = input.length();
	if (size == 1) return 1;
	int start = 0, end = 0;
	while (start < size) {
		char c = input.charAt(start);
		while (end < size && c == input.charAt(end)) end++;
		if (end >= size) {
			operations = Math.min(operations, strangePrinter(input.substring(0, start)) + 1);
		} else {
			operations = Math.min(operations, strangePrinter(input.substring(0, start) + input.substring(end)) + 1);
		}
		start = end;
	}
	map.put(input, operations);
	return operations;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
	val memo = mutableMapOf<String, Int>()
	fun strangePrinter(s: String): Int {
		fun dfs(input: String): Int {
			if (input.isEmpty()) return 0
			if (input.length == 1) return 1
			memo[input]?.let { return it }
			var operations = input.length
			var start = 0
			var end = 0
			val n = input.length
			while (start < n) {
				val c = input[start]
				while (end < n && input[end] == c) end++
				if (end >= n)
					operations = minOf(operations, dfs(input.substring(0, start)) + 1)
				else
					operations = minOf(operations, dfs(input.substring(0, start) + input.substring(end)) + 1)
				start = end
			}
			memo[input] = operations
			return operations
		}
		return dfs(s)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
	def strangePrinter(self, s: str) -> int:
		memo = {}
		def dfs(input: str) -> int:
			if not input:
				return 0
			if len(input) == 1:
				return 1
			if input in memo:
				return memo[input]
			operations = len(input)
			start, end = 0, 0
			n = len(input)
			while start < n:
				c = input[start]
				while end < n and input[end] == c:
					end += 1
				if end >= n:
					operations = min(operations, dfs(input[:start]) + 1)
				else:
					operations = min(operations, dfs(input[:start] + input[end:]) + 1)
				start = end
			memo[input] = operations
			return operations
		return dfs(s)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
use std::collections::HashMap;
impl Solution {
	pub fn strange_printer(s: String) -> i32 {
		fn dfs(input: &str, memo: &mut HashMap<String, i32>) -> i32 {
			if input.is_empty() { return 0; }
			if input.len() == 1 { return 1; }
			if let Some(&v) = memo.get(input) { return v; }
			let mut operations = input.len() as i32;
			let n = input.len();
			let bytes = input.as_bytes();
			let mut start = 0;
			while start < n {
				let c = bytes[start];
				let mut end = start;
				while end < n && bytes[end] == c { end += 1; }
				if end >= n {
					operations = operations.min(dfs(&input[..start], memo) + 1);
				} else {
					operations = operations.min(dfs(&[&input[..start], &input[end..]].concat(), memo) + 1);
				}
				start = end;
			}
			memo.insert(input.to_string(), operations);
			operations
		}
		let mut memo = HashMap::new();
		dfs(&s, &mut memo)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function strangePrinter(s: string): number {
	const memo: Record<string, number> = {};
	function dfs(input: string): number {
		if (!input) return 0;
		if (input.length === 1) return 1;
		if (input in memo) return memo[input];
		let operations = input.length;
		let start = 0, end = 0, n = input.length;
		while (start < n) {
			const c = input[start];
			while (end < n && input[end] === c) end++;
			if (end >= n)
				operations = Math.min(operations, dfs(input.slice(0, start)) + 1);
			else
				operations = Math.min(operations, dfs(input.slice(0, start) + input.slice(end)) + 1);
			start = end;
		}
		memo[input] = operations;
		return operations;
	}
	return dfs(s);
}

Complexity

  • ⏰ 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 table where `dp[i][j]` is the minimum turns needed to print the substring from index `i` to `j`. We fill the table iteratively, considering all possible splits and merges of identical characters.

#### Approach

Initialize a 2D DP table. For each 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
	int strangePrinter(string s) {
		int n = s.length();
		if (n == 0) return 0;
		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];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func strangePrinter(s string) int {
	n := len(s)
	if n == 0 {
		return 0
	}
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}
	for l := 1; l < n; l++ {
		for i := 0; i+l < n; i++ {
			j := i + l
			dp[i][j] = l + 1
			for k := i; k < j; k++ {
				temp := dp[i][k] + dp[k+1][j]
				if s[k] == s[j] {
					temp--
				}
				if temp < dp[i][j] {
					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
19
20
21
22
23
24
25
public int strangePrinter(String s) {
	if (s == null || s.length() == 0) return 0;
	int n = s.length();
	int[][] dp = new int[n][n];
	for (int i = 0; i < n; i++) {
		dp[i][i] = 1;
		if (i < n - 1) {
			dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 1 : 2;
		}
	}
	for (int len = 2; len < n; len++) {
		for (int start = 0; start + len < n; start++) {
			int end = start + len;
			dp[start][end] = len + 1;
			for (int k = 0; k < len; k++) {
				int temp = dp[start][start + k] + dp[start + k + 1][end];
				dp[start][end] = Math.min(
					dp[start][end],
					s.charAt(start + k) == s.charAt(end) ? temp - 1 : temp
				);
			}
		}
	}
	return dp[0][n - 1];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
	fun strangePrinter(s: String): Int {
		val n = s.length
		if (n == 0) return 0
		val dp = Array(n) { IntArray(n) }
		for (i in 0 until n) dp[i][i] = 1
		for (len in 1 until n) {
			for (i in 0 until n - len) {
				val j = i + len
				dp[i][j] = len + 1
				for (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
class Solution:
	def strangePrinter(self, s: str) -> int:
		n = len(s)
		if n == 0:
			return 0
		dp = [[0]*n for _ in range(n)]
		for i in range(n):
			dp[i][i] = 1
		for l in range(1, n):
			for i in range(n-l):
				j = i + l
				dp[i][j] = l + 1
				for 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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
	pub fn strange_printer(s: String) -> i32 {
		let n = s.len();
		if n == 0 { return 0; }
		let bytes = s.as_bytes();
		let mut dp = vec![vec![0; n]; n];
		for i in 0..n { dp[i][i] = 1; }
		for l in 1..n {
			for i in 0..n-l {
				let j = i + l;
				dp[i][j] = l as i32 + 1;
				for k in i..j {
					let mut 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
function strangePrinter(s: string): number {
	const n = s.length;
	if (n === 0) return 0;
	const dp: number[][] = Array.from({length: n}, () => Array(n).fill(0));
	for (let i = 0; i < n; i++) dp[i][i] = 1;
	for (let l = 1; l < n; l++) {
		for (let i = 0; i + l < n; i++) {
			const j = i + l;
			dp[i][j] = l + 1;
			for (let k = i; k < j; k++) {
				let temp = dp[i][k] + dp[k+1][j];
				if (s[k] === s[j]) temp--;
				dp[i][j] = Math.min(dp[i][j], temp);
			}
		}
	}
	return dp[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.