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

/*
We can kind of think about this like applying a bunch of layers. Tricky part is when we have
overlapping gaps:

AABBAABB -> which do we cover up? In this case it's trivial, but if we have:

AABBBAABB actually this is also trivial.

The frequency of consecutive letters doesn't matter because it's the same cost. 

ABABCBCBA - we should _not_ paint from the first A to the last A

Some sort of invariant of for each subarray only print the most frequent letter as the base.
Seems too complicated. What should the very base layer be? Should always just be the first letter.

Hypothesis: we should always repaint from first to last position of a given letter. Not really the case.
Too simple. But why doesn't this work? 

Greedily do it - greedy seems to give non-optimal. So let's do it with DP perhaps.

What uniquely defines our current state ? I suppose all of the current bands that we've placed.
Perhaps all of the letters that we've done? 

dp(i,j) := the cost to print s[i:j]. At each position, we are currently at the char c, 
we can paint up through any number of c's.
*/

class Solution {
private:
    std::vector<std::vector<std::optional<int>>> memo;
    std::unordered_map<char, std::vector<size_t>> appearances;
    string s;

    size_t backtrack(size_t startPos, size_t endPos)
    {
        if(memo[startPos][endPos].has_value())
        {
            return *memo[startPos][endPos];
        }
        memo[startPos][endPos] = [&]() -> size_t
        {
            if(startPos == endPos)
            {
                return 1;
            }
            // heart of our logic
            if(s[startPos] == s[endPos])
            {
                return backtrack(startPos, endPos - 1);
            }

            size_t res = 1 + backtrack(startPos, endPos - 1);

            // for some reason this overcounts when endPos - 1 == endPos
            for(size_t i = startPos + 1; i < endPos; ++i) 
            {
                if(s[i] == s[endPos])
                    res = min(res, backtrack(startPos, i - 1) + backtrack(i, endPos));
            }
            return res;
        }();

        return *memo[startPos][endPos];
    }
public:
    int strangePrinter(string inputS) {
        s = inputS;
        
        [&inputS](){
            string res = {inputS.front()};

            for(auto it = ++inputS.begin(); it != inputS.end(); ++it)
            {
                if(*it != res.back())
                {
                    res.push_back(*it);
                }
            }    

            return res;
        }();

        memo = vector<vector<optional<int>>>(s.size() + 1, vector<optional<int>>(s.size() + 1, std::nullopt));
        for(size_t i = 0; i < s.size(); ++i)
        {
            appearances[s[i]].push_back(i);
        }

        return backtrack(0, s.size() - 1);
    }
};

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
15902