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

/*
EXAMPLE
aaa -> aba
aaaaa -> abbba -> ababa

SOLUTION
partition dp
-> string segemnt [l...r]
for the segment -> move l till we get new element [l'.... r]

1. 1 + f(l', r) -> print the first letter seperately and solve for remaining segment 

2. go for patrition where s[k] == s[l] -> this means that this letter can be printed with the prvious printed one


f(l, r, prev_same)   prev_same == true if s[l] is same as the previous s[l] from which it came 
-> we do not neet to print this seperately

-> solve recursively




*/


class Solution {
public:

    int solve(int l, int r, bool prev_same, string &s, vector<vector<vector<int>>> &dp){

        if(l==r) return prev_same == false;
        if(l>r) return 0;

        if(dp[l][r][prev_same] != -1) return dp[l][r][prev_same];

        char start = s[l];

        int l_temp = l;

        while(s[l] == start) l++;
        l--;
        // if now l>r -> need to do something -> return 1 if not same as previous
        // if(l > r) return prev_same == false;

        // print this and solve for ahead
        int ans = solve(l+1, r, false, s, dp);

        if(prev_same == false) {
            // need to print the char and solve for ahead
            ans += 1;
            // if true -> do not need to add -> already printed before
        }

        // look for some other character and do the partition
        for(int k=l+1; k<=r; k++){

            // do this only if s[k] == start
            if(s[k] == start){
                // we have found a char same as the start
                //      solve for l+1..k-1 (different)   solve for k...r (s[k] == start)
                int temp = solve(l+1, k-1, false, s, dp) +  solve(k, r, true, s, dp);

                if(prev_same == false) temp ++;

                ans = min(ans, temp);

            }
        }

        // cout << l << " " << r << " prev_same: " << prev_same << " ans=" << ans << endl;
 
        return dp[l][r][prev_same] = ans;
    }

    int strangePrinter(string s) {

        int n = s.size();

        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(2, -1)));

        return solve(0, n-1, false, s, dp);

    }
};
41857