<p>There is a strange printer with the following two special properties:</p>

<ul>
	<li>The printer can only print a sequence of <strong>the same character</strong> each time.</li>
	<li>At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.</li>
</ul>

<p>Given a string <code>s</code>, return <em>the minimum number of turns the printer needed to print it</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaabbb&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> Print &quot;aaa&quot; first and then print &quot;bbb&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aba&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> Print &quot;aaa&quot; first and then print &quot;b&quot; from the second place of the string, which will cover the existing character &#39;a&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def strangePrinter_ERR(self, s: str) -> int:
        """
        count largest group and then sort them and then print them
        aabcbacc
        abbaba
        how to group it 
        how many: 26 turns?
        """
        grp = defaultdict(int)
        pre = None

        for c in s:
            if c != pre:grp[c] += 1
            pre = c

        arr = sorted([[c, grp[c]] for c in grp], key=lambda x: -x[1])
        print(arr)

        seen = set()
        def dfs(i):
            if i == len(arr): return 0            
            #do not overwrite the previous seen, other than that can connect grp and write long
            cur = arr[i][0]
            cnt = 0
            wrt = 0
            for c in s:                
                if c in seen and wrt:                     
                    wrt = 0
                elif c == cur and wrt == 0:
                    cnt += 1
                    wrt = 1
                print(c, cur, cnt, wrt)
            seen.add(cur)
            #print(cur, cnt)
            return cnt + dfs(i+1)
        
        return dfs(0)


    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[inf] * n for _ in range(n)]
        for i in range(n): dp[i][i] = 1

        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i][j-1]
                else:
                    for k in range(i, j):
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) #[[i, k], [k+1, j]]
        
        print(dp)
        return dp[0][n-1]
                
    def strangePrinter(self, s: str) -> int:
        n = len(s)

        @cache
        def dfs(i, j):
            if j < i: return 0            
            if j == i: return 1
            else:
                if s[i] == s[j]: return min(dfs(i+1, j), dfs(i, j-1))
                else:
                    ans = inf
                    for k in range(i, j):
                        ans = min(ans, dfs(i, k) + dfs(k+1,j))
                    return ans

        return dfs(0, n-1)


20400