Strange Printer

hard dp interval

Problem

Each turn the printer prints one char repeated, possibly overwriting. Minimum turns to print s.

Inputs = 'aaabbb'

Output2

Print 'aaaaaa' then overwrite with 'bbb'.

input

def strange_printer(s):
    n = len(s); dp = [[0]*n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    for L in range(2, n + 1):
        for i in range(n - L + 1):
            j = i + L - 1; dp[i][j] = dp[i][j - 1] + 1
            for k in range(i, j):
                if s[k] == s[j]: dp[i][j] = min(dp[i][j], dp[i][k] + (dp[k+1][j-1] if k + 1 <= j - 1 else 0))
    return dp[0][n - 1]

function strangePrinter(s) {
  const n = s.length; const dp = Array.from({length: n}, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = 1;
  for (let L = 2; L <= n; L++)
    for (let i = 0; i + L - 1 < n; i++) {
      const j = i + L - 1; dp[i][j] = dp[i][j - 1] + 1;
      for (let k = i; k < j; k++)
        if (s[k] === s[j]) dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k+1][j-1] : 0));
    }
  return dp[0][n - 1];
}

int strangePrinter(String s) {
    int n = s.length(); int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int L = 2; L <= n; L++)
        for (int i = 0; i + L - 1 < n; i++) {
            int j = i + L - 1; dp[i][j] = dp[i][j - 1] + 1;
            for (int k = i; k < j; k++)
                if (s.charAt(k) == s.charAt(j)) dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k+1][j-1] : 0));
        }
    return dp[0][n - 1];
}

int strangePrinter(string s) {
    int n = s.size(); vector> dp(n, vector(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int L = 2; L <= n; L++)
        for (int i = 0; i + L - 1 < n; i++) {
            int j = i + L - 1; dp[i][j] = dp[i][j - 1] + 1;
            for (int k = i; k < j; k++)
                if (s[k] == s[j]) dp[i][j] = min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k+1][j-1] : 0));
        }
    return dp[0][n - 1];
}

Explanation

Each print covers a contiguous run of one character (possibly overwriting later), and we want the fewest prints to produce s. This is interval DP: dp[i][j] is the minimum prints needed for the substring s[i..j].

A single character needs one print, so dp[i][i] = 1. For a longer interval, a safe baseline is to print s[j] on its own: dp[i][j] = dp[i][j-1] + 1.

The savings come from matching characters. If some earlier position k has s[k] == s[j], then the print that lays down s[k] can be stretched to also cover position j for free. That merges the two pieces: dp[i][k] + dp[k+1][j-1]. We take the minimum over all such k.

Example: s = 'aaabbb'. First print 'aaaaaa' across the whole thing (1 print), then overwrite the last three with 'bbb' (1 print) — total 2. The matching-character merge is what keeps it at 2 instead of more.

We fill intervals by increasing length so that the smaller pieces are already solved. With n² intervals and an inner scan over k, the cost is O(n³).

Time: O(n³) Space: O(n²)