<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 std::string& s) const
    {
        std::vector<std::vector<std::optional<int>>> cache;
        cache.resize(s.size(), std::vector<std::optional<int>>(s.size()));

        const auto solve = [&](char current, std::string_view target, auto rec)
        {
            if(target.empty())
                return 0;
            
            if(current==target.front())
            {
                int skip = 0;
                while(skip<target.size() && current==target[skip])
                    ++skip;
                
                return rec(current, target.substr(skip), rec);
            }

            while(current==target.back())
                target = target.substr(0,target.size()-1);

            const auto start_idx = target.data() - s.data();
            const auto end_idx = target.data() - s.data() + target.size()-1;
            if(auto cache_entry = cache[start_idx][end_idx]; cache_entry)
                return *cache_entry;
            
            int min = rec(target.front(),target.substr(1),rec);
            for(std::size_t i=1; i<target.size(); ++i)
            {
//                if(current!=target.front())
                {
                    const auto to_here = rec(target.front(),target.substr(0,i), rec);
                    const auto after = rec(current, target.substr(i),rec);
                    min = std::min(min, to_here+after);
                }
            }

            return *(cache[start_idx][end_idx] = 1 + min);
        };

        return solve('.',s, solve);
    }
};
15007