<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>

#include <string>
#include <vector>

using std::string, std::vector;

inline constexpr size_t MAX_LEN = 100;

class Solution {
    vector<int> mins;

public:
    int strangePrinter(string input) {
        mins = vector<int>((MAX_LEN + 1) * (MAX_LEN + 1), -1);
        string str = remove_repeated(input);
        return min_turns(str, 0, str.size());
    }

private:
    string remove_repeated(const string& str) {
        string result;
        result.reserve(str.size());
        for (char c : str) {
            if (!result.empty() && c == result.back()) {
                continue;
            }
            result.push_back(c);
        }
        return result;
    }

    int min_turns(const string& str, size_t start, size_t end) {
        if (end - start <= 2) {
            return end - start;
        }
        size_t key = hash_state(start, end);
        if (mins[key] != -1) {
            return mins[key];
        }

        int min = min_turns(str, start + 1, end) + 1;
        for (size_t mid = start + 2; mid < end; mid ++) {
            if (str[mid] == str[start]) {
                int spliced = min_turns(str, start, mid) + min_turns(str, mid + 1, end);
                min = std::min(spliced, min);
            }
        }

        mins[key] = min;
        return min;
    }

    inline constexpr size_t hash_state(size_t start, size_t end) {
        return start * (MAX_LEN + 1) + end;
    }
};
17692