<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) {
        if (s.size() == 1)
            return 1;

        if (s.size() == 2) {
            return (s[0] != s[1]) + 1;
        }
        int result = impl(string_view(s));
        return result;

    }

private:
    unordered_map<string_view, int> cache;

    int impl(const string_view& s) {
        if (s.size() == 1)
            return 1;

        if (s.size() == 2) {
            return (s[0] == s[1]) ? 1 : 2;
        }

        int i = 1;
        while(i < s.size() and s[i] == s[0]) ++i;
        if (i == s.size())
            return 1;

        const auto it = cache.find(s);
        if (it != cache.end())
            return it->second;

            
        int l = i;
        int l0 = l;
        int result = impl(s.substr(l)) + 1;

        // "lllolllelll"
        // lsubcost will be cost("o") + cost("e") so that total result = 3.
        int lsubcost = 0;
        while(i < s.size()) {
            if (s[i] != s[0]) {
                ++i;
                continue;
            }
            int r = i;
            while(i < s.size() and s[i] == s[0]) ++i;
 
            // impl(s.substr(0, r)) means treating "bacbcab" as "all b" + "a..a" + "c..c" + "b" (i.e. pyramid)
            // NOT inner substring l0 .. r0 because recursive all needs to know sides, therefore -1 here.
            result= min(result, impl(s.substr(0, r)) -1 +1 + (i < s.size() ? impl(s.substr(i)) : 0));
        }
        cache[s] = result;
        return result;
    }
};


24852