<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(std::string &s) {
        int size{ static_cast<int>(s.size()) };

        {
            int i{ 0 };

            for (int j{ 1 }; j < size; ++j) {
                if (s[i] != s[j]) { s[++i] = s[j]; }
            }

            size = i + 1;
            s.resize(size);
        }

        if (size == 1) { return 1; }

        std::vector<std::vector<int>> dp[27];

        for (int ab{ 0 }; ab < 27; ++ab) {
            dp[ab].resize(size + 1);
            dp[ab][0].resize(size + 1, 0);

            for (int l{ 1 }; l <= size; ++l) { dp[ab][l].resize(size + 1 - l); }

            for (int i{ 0 }; i < size; ++i) { dp[ab][1][i] = s[i] - 'a' != ab; }
        }

        for (int l{ 2 }; l <= size; ++l) {
            for (int ab{ 0 }; ab < 27; ++ab) {
                for (int i{ 0 }; i + l <= size; ++i) {
                    int j{ i + l };

                    int cd{ s[i] - 'a' };

                    if (ab == cd) {
                        dp[ab][l][i] = dp[ab][l - 1][i + 1];
                        continue;
                    }

                    int ans{ cd == s[j - 1] - 'a' ? 1 + dp[cd][l - 2][i + 1]
                                                  : INT_MAX };

                    for (int k{ i + 1 }; k < j; ++k) {
                        ans = std::min(ans,
                                       1 + dp[cd][k - i][i] + dp[ab][j - k][k]);
                    }

                    dp[ab][l][i] = ans;
                }
            }
        }

        return dp[26][size][0];
    }
};

46332