<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 {
    unordered_map<int,int> dp;
public:
    int strangePrinter(const string& s, int start = 0, int len = -1, int exc = '-') {
        if (len == -1) len = s.size();
        if (len == 0) return 0;
        if (len == 1) {
            if (s[start]==exc) return 0;
            return 1;
        }
        int dpK = start | (len<<8) | (exc<<16);
        auto dpI = dp.find(dpK);
        if (dpI != dp.end()) return dpI->second;
        int res = 1e9;
        int state = 0, d = 0;
        int add = 1;
        if (exc == s[start]) add = 0;
        for (int i = start; i < start+len; i++) {
            if (state == 0) {
                if (s[i] == s[start]) {
                    res = min(res, add+strangePrinter(s,i+1,start+len-i-1,exc));
                } else {
                    d = i;
                    state = 1;
                }
            } else {
                if (s[i] == s[start]) {
                    int i0 = i;
                    while (i <start+len && s[i]==s[start]) i++;
                    res = min(res, add+strangePrinter(s,d,i0-d, s[start])
                    + strangePrinter(s,i,start+len-i,exc));
                    i--;
                }
            }
        }
        dp[dpK] = res;
        return res;
    }
};

21272