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

        string ss = "";
        ss.push_back(s[0]);

        for(int i=1;i<s.length();i++)
        {
            if(s[i]!=ss.back())
            {
                ss.push_back(s[i]);
            }
        }

        // i have ss
        // cout<<ss<<endl;

        int n=ss.length();
        vector<vector<int>>dp(n+1,vector<int>(n+1,0));
        int ans = solver(ss,0,n-1,dp);
        return(ans);
        
    }
    int solver(string &ss , int start,int end,vector<vector<int>>&dp)
    {
        // cout<<start<<" "<<end<<endl;
        if(start>end)return(0);
        if(start==end)return(1);
        if(dp[start][end]!=0)return(dp[start][end]);

        unordered_map<char,vector<int>>m;
        vector<int>v(end-start+1,INT_MAX);
        v[0]=1;
        m[ss[start]].push_back(start);

        for(int i=start+1;i<=end;i++)
        {
            if(m.find(ss[i])==m.end())
            {
                v[i-start]=v[i-start-1]+1;
                // m[ss[i]].push_back(i);
            }
            else
            {
                // cout<<"innnnnnn"<<" "<<i<<endl;
                int prev;
                for(int val : m[ss[i]])
                {
                    // cout<<" oooooooo"<<endl;
                    prev=v[val-start];
                    v[i-start]=min(v[i-start],prev+solver(ss,val+1,i-1,dp));

                }
            }
            v[i-start]=min(v[i-start],1+v[i-start-1]);
            dp[start][i]=v[i-start];
            
            m[ss[i]].push_back(i);
        }
        // cout<<start<<" "<<end<<" "<<v[v.size()-1]<<endl;
        
        return(v[v.size()-1]);
    }
};


// abcdefghijklabcdefghijkmkjabsdbaskdjbakjcbkjasbakhsbdhbahd

// aaabbcbcaab --- abcbcab
// 11122334445

// abcdbadcb
// abcdefghijklabcdefghijkm

// abcdbadcb
// 123444566




// class Solution {
// public:
//     int strangePrinter(string s) {

//         string ss = "";
//         ss.push_back(s[0]);

//         for(int i=1;i<s.length();i++)
//         {
//             if(s[i]!=ss.back())
//             {
//                 ss.push_back(s[i]);
//             }
//         }

//         // i have ss
//         // cout<<ss<<endl;

//         int n=ss.length();
//         // vector<vector<int>>dp(n,vector<int>(n,0));
//         int ans = solver(ss,0,n-1);
//         return(ans);
        
//     }
//     int solver(string &ss , int start,int end)
//     {
//         if(start>end)return(0);
//         if(start==end)return(1);
//         unordered_map<char,int>m;
//         vector<int>v(end-start+1,0);
//         v[0]=1;
//         m[ss[start]]=start;

//         for(int i=start+1;i<=end;i++)
//         {
//             if(m.find(ss[i])==m.end())
//             {
//                 v[i-start]=v[i-start-1]+1;
//                 m[ss[i]]=i;
//             }
//             else
//             {
//                 // cout<<"innnnnnn"<<" "<<i<<endl;
//                 int prev=0;
//                 // if(m[ss[i]]!=0)
//                 // {
//                     prev=v[m[ss[i]]-start];
//                 // }
//                 v[i-start]=prev+solver(ss,m[ss[i]]+1,i-1);
//             }
//             v[i-start]=min(v[i-start],1+v[i-start-1]);
            
//             // m[ss[i]]=i;
//         }
//         // cout<<start<<" "<<end<<" "<<v[v.size()-1]<<endl;
//         return(v[v.size()-1]);
//     }
// };




// // aaabbcbcaab --- abcbcab
// // 11122334445

// // abcdbadcb
// // abcdefghijklabcdefghijkm

// // abcdbadcb
// // 123444566
37382