1
# Runtime: 878 ms (Top 47.91%) | Memory: 16.1 MB (Top 47.44%)
2
class Solution(object):
3
    def strangePrinter(self, s):
4
        """
5
        :type s: str
6
        :rtype: int
7
        """
8
        # remove duplicate letters from s.
9
        tmp = []
10
        for c in s:
11
            if len(tmp) == 0 or tmp[-1] != c:
12
                tmp.append(c)
13
        s = "".join(tmp)
14

15
        _m = {}
16

17
        def _dp(i, j, background):
18
            if j < i:
19
                return 0
20
            elif i == j:
21
                return 1 if background != s[i] else 0
22
            elif (i, j, background) in _m:
23
                return _m[(i, j, background)]
24

25
            ans = len(s)
26

27
            # shrink s[i:j+1] to s[i_:j_+1] according to the background letter
28
            i_ = i + 1 if s[i] == background else i
29
            j_ = j - 1 if s[j] == background else j
30

31
            if s[i_] == s[j_]:
32
                # case "AxxxA" => best strategy is printing A first
33
                ans = _dp(i_ + 1, j_ - 1, s[i_]) + 1
34
            else:
35
                # otherwise, print first letter, try every possible print length
36
                for p in range(i_, j_ + 1):
37
                    # searching is needed only if s[p] == s[i_]
38
                    # e.g. s="ABCDEA"print 'A' on s[0:1] is equivalent to s[0:5]
39
                    if s[p] != s[i_]:
40
                        continue
41
                    l = _dp(i_, p, s[i_])
42
                    r = _dp(p + 1, j_, background)
43
                    ans = min(ans, l + r + 1)
44
            _m[(i, j, background)] = ans
45
            return ans
46

47
        return _dp(0, len(s) - 1, "")