DSA problem
Strange Printer
There is a strange printer that can only print sequences of the same character. Each turn it picks one character and prints a contiguous run of that character on the paper. It may print a new run that covers previously printed positions, overwriting them. Given a string s, return the minimum number of turns the printer needs to print exactly s.
The optimal strategy hinges on an interval-DP insight: collapse any run of equal characters first, because printing "aaab" takes the same number of turns as "ab" (you simply make the first run longer). After that simplification, define dp[i][j] as the minimum turns required to print the substring s[i..j].
The recurrence has two cases. The default is to print s[i] alone and then recursively print s[i+1..j], costing 1 + dp[i+1][j] turns. The improvement comes when there is some k with i < k <= j and s[k] = s[i]: we can extend the very first turn that printed s[i] to cover position k too, saving one turn. Concretely, dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) — the cost of printing the middle slice plus the suffix, with the suffix reusing the initial s[i] print at position k instead of paying for it separately.
Fill the table by interval length from 1 to n, with base case dp[i][i] = 1. The answer is dp[0][n-1]. Time complexity is O(n³) and space is O(n²), which is comfortable for the constraint n <= 100.
Examples
s = "aaabbb"2s = "aba"2s = "abcabc"5Constraints
- 1 <= s.length <= 100
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.