```
class Solution(object):
def strangePrinter(self, s):
if not s:
return 0
#reduce the input
fs = s[0]
for i in range(1, len(s)):
if s[i] != s[i - 1]:
fs += s[i]
l = len(fs)
dp = [[0xffffffff for i in range(l)] for j in range(l)]
for i in range(l):
dp[i][i] = 1
for i in range(l):
for j in range(i - 1, -1, -1):
if fs[i] == fs[j]:
dp[i][j] = min(dp[i - 1][j + 1] + 1, dp[i - 1][j], dp[i][j + 1])
else:
for x in range(j + 1, i + 1):
dp[i][j] = min(dp[i][x] + dp[x - 1][j], dp[i][j])
return dp[-1][0]
```