<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 {
public:
    int strangePrinter(const string& s) {
        vector<vector<int>> dp(s.size());
        for (auto& row : dp) row.resize(s.size() + 1, -1);
        return find(s, 0, s.size(), dp);
    }
    
    int find(const string& s, int lo, int hi, vector<vector<int>>& dp) {
        if (lo == hi) return 0;
        if (lo + 1 == hi) return 1;
        if (dp[lo][hi] >= 0) return dp[lo][hi];
        
        vector<pair<int, int>> ints;
        int i = lo, j;
        while (i < hi && s[i] == s[lo]) ++i;

        while (i < hi) {
            j = i;
            while (i < hi && s[i] != s[lo]) ++i;
            ints.emplace_back(j, i);
            while (i < hi && s[i] == s[lo]) ++i;
        }
        
        return dp[lo][hi] = 1 + find_vec(s, ints, 0, dp);
    }
    
    int find_vec(const string& s, const vector<pair<int, int>>& ints, int vlo, vector<vector<int>>& dp) {
        if (vlo == ints.size()) return 0;
        if (vlo + 1 == ints.size()) return find(s, ints.back().first, ints.back().second, dp);
        
        int lo = ints[vlo].first, hi, best = INT32_MAX;
        for (int i = vlo; i < ints.size(); ++i) {
            hi = ints[i].second;
            best = min(best, find(s, lo, hi, dp) + find_vec(s, ints, i + 1, dp));
        }
        
        return best;
    }
};
44542