1
var strangePrinter = function (s) {
2
  if (!s) return 0;
3

4
  const N = s.length;
5
  const state = Array.from({ length: N }, () => Array.from({ length: N }));
6

7
  for (let i = 0; i < N; i++) {
8
    // Printing one character always takes one attempt
9
    state[i][i] = 1;
10
  }
11

12
  const search = (i, j) => {
13
    if (state[i][j]) return state[i][j];
14

15
    state[i][j] = Infinity;
16
    for (let k = i; k < j; k++) {
17
      state[i][j] = Math.min(state[i][j], search(i, k) + search(k + 1, j));
18
    }
19
    if (s[i] === s[j]) state[i][j]--;
20
    return state[i][j];
21
  };
22

23
  return search(0, N - 1);
24
};