<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(string s)
    {
        // holds the number of turns needed to print from start to end indices encoded as a string "start-end"
        unordered_map<string, int> dp;
        // remove duplicate consecutive characters (aaaabbbb -> ab) or (aaaabbbbaaa -> aba)
        // unique(): each group of consecutive duplicate elements is reduced to a single element
        // unique() does not actually remove the duplicates,
        // it simply moves them to the end of the string
        // and returns an iterator pointing to the new logical end of the string,
        // which is where the first duplicate element was moved
        auto endOfUniqueIterator = unique(s.begin(), s.end());
        // this is just an optimization since consecutive duplicate elements will not affect the result
        s.erase(endOfUniqueIterator, s.end());
        n = s.size();
        return dfs(0, n - 1, s, dp);
    }

private:
    int n = 0;

    int dfs(int start, int end, const string &s, unordered_map<string, int> &dp)
    {
        if (start > end)
            return 0;

        string key = to_string(start) + "-" + to_string(end);
        if (dp.count(key))
            return dp[key];

        // we can remove only the last character
        int res = dfs(start, end - 1, s, dp) + 1;

        for (int middle = start; middle < end; middle++)
        {
            // if the middle character is the same as the last character,
            // then we can print from middle to end to remove at least two characters in one print
            if (s[middle] == s[end])
            {
                // we actually keep the middle character in the left partition
                // because it may also hit the condition of s[mid] == s[end]
                // where the current mid is the end in the recursive call with left
                // if this were to happen it would save us a print from printing the left most character
                int left = dfs(start, middle, s, dp);
                // we can remove middle and last character in one print
                int right = dfs(middle + 1, end - 1, s, dp);
                res = min(res, left + right);
            }
        }

        dp[key] = res;
        return res;
    }
};
30222