AlgoMaster Logo

Strange Printer

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This problem asks us to figure out the minimum number of "turns" a special printer needs to print a given string. Each turn, the printer picks one character and prints it over a contiguous range of positions. Later prints overwrite earlier ones.

Because later turns overwrite earlier ones, the optimal strategy often prints a character across a wide range first and overwrites the middle portions later. To print "aba", you print "aaa" across all three positions, then overwrite position 1 with "b". That is 2 turns, not 3.

This structure leads to interval DP. We want the minimum number of turns to print any substring s[i..j]. When the first and last characters of a substring match, the first character's print can extend to cover the last position at no extra cost, which reduces the problem size. When they do not match, we try all split points and take the one that minimizes total turns.

Key Constraints

  • 1 <= s.length <= 100: with n up to 100, an O(n^3) algorithm runs in about 10^6 operations, well within limits. This is the range where interval DP is the standard fit.
  • s consists of lowercase English letters: the alphabet is small, but the approach does not depend on it. The same DP works for any character set.

Approach 1: Recursive Brute Force with Memoization (Top-Down DP)

Intuition

Think about the problem recursively. To print the substring s[i..j], we make at least one turn, and we can print the character s[i] across the range in that first turn, then account for the remaining turns.

When s[i] == s[j], the first turn that prints s[i] can extend all the way to position j at no extra cost. So printing s[i..j] costs the same as printing s[i..j-1]: the character at position j is already covered by extending the initial print.

When s[i] != s[j], no single turn covers both endpoints with their final characters, so we split the problem at some index k into s[i..k] and s[k+1..j] and add the cost of solving both halves. Trying every split point and taking the minimum gives the optimal total.

Algorithm

  1. Define a recursive function solve(i, j) that returns the minimum turns to print s[i..j].
  2. Base case: if i > j, return 0. If i == j, return 1 (a single character needs exactly one turn).
  3. If s[i] == s[j], return solve(i, j-1) because we can extend the first character's print.
  4. Otherwise, try every split point k from i to j-1. For each split, compute solve(i, k) + solve(k+1, j). Return the minimum across all splits.
  5. Memoize results to avoid recomputation.

Visualization and Code

Loading animation...

This runs in O(n^3), which is acceptable for n <= 100. The same recurrence can also be filled iteratively, which removes recursion overhead and makes the evaluation order explicit.

Approach 2: Bottom-Up Interval DP

Intuition

The recurrence is the same as the top-down version, filled iteratively. dp[i][j] is the minimum turns to print s[i..j]. We compute entries by increasing interval length so every subproblem an entry depends on is already filled. A single character gives dp[i][i] = 1. For longer intervals, if s[i] == s[j] then dp[i][j] = dp[i][j-1]; otherwise we try all split points.

The ordering by interval length is what makes the iterative version correct. The value dp[i][j] depends only on shorter intervals: dp[i][j-1] in the matching case, and dp[i][k] and dp[k+1][j] in the splitting case. Each of those covers fewer characters than [i, j], so they are all computed before dp[i][j] is reached.

Algorithm

  1. Initialize a 2D array dp of size n x n with all zeros.
  2. Set dp[i][i] = 1 for all i (every single character needs one turn).
  3. For each interval length len from 2 to n:
    • For each starting index i from 0 to n - len:
      • Set j = i + len - 1.
      • If s[i] == s[j], set dp[i][j] = dp[i][j-1].
      • Otherwise, set dp[i][j] = len (worst case), then try all split points k from i to j-1 and update dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]).
  4. Return dp[0][n-1].

Visualization and Code

Loading animation...

Both approaches so far are O(n^3) in the original string length. Consecutive duplicate characters like the "aaa" in "aaabbba" cost no extra turns, yet they inflate n and create subproblems that resolve to the same value. Compressing runs of identical characters before running the DP shrinks n directly, which lowers the constant and often the asymptotic cost on real inputs.

Approach 3: Optimized Interval DP with Duplicate Removal

Intuition

A run of identical characters costs one turn. Printing "aaa" takes the same number of turns as printing "a", since the printer covers a contiguous range of one character in a single turn. So "aaabbbccc" needs the same number of turns as "abc".

Removing consecutive duplicates before running the DP shrinks the effective length. "aaabbbcccaaabbb" (length 15) compresses to "abcab" (length 5), turning an O(15^3) problem into O(5^3).

This approach also uses a different recurrence. Instead of comparing only the two endpoints, it anchors on the first character t[i] and looks for any later position m in the interval where t[m] == t[i]. The turn that prints t[i] can extend past m in one stroke, which lets the interval split as dp[i][j] = dp[i+1][m] + dp[m+1][j].

Algorithm

  1. Remove consecutive duplicate characters from s to get a compressed string t.
  2. Let n be the length of t.
  3. Initialize dp[i][i] = 1 for all i.
  4. For each interval length from 2 to n:
    • For each starting index i:
      • Set j = i + len - 1.
      • Start with dp[i][j] = dp[i+1][j] + 1 (print t[i] alone, then handle the rest).
      • For each m from i+1 to j, if t[m] == t[i], try dp[i][j] = min(dp[i][j], dp[i+1][m] + dp[m+1][j]).
  5. Return dp[0][n-1].

Visualization and Code

Loading animation...