<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:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[-1 for i in range(n)]for i in range(n)]
        def solve(l,r):
            # It takes only one op to print a single ch
            if l == r:
                return 1
            # all ch are exhausted
            if l>r:
                return 0
            if dp[l][r]!=-1:
                return dp[l][r]
            # One way is to print ch as we go, if we find same ch print them using one op and as soon as we find a fidd ch we go to that ind and ask recursion for the remaining. If i == r+1 that means the whole string has duplicate ch equal to s[l] that means we need only 1 op to print this
            i = l+1
            while i<=r and s[i] == s[l]:
                i+=1
            if i == r+1:
                return 1
            basic = 1+solve(i,r)
            # we can use another approach as in eg 2 "aba" we can also print "aaa" first and then print "b" after this
            greedy = float('inf')
            for j in range(i,r+1):
                if s[j] == s[l]:
                    greedy = min(greedy,solve(i,j-1)+solve(j,r))
            dp[l][r] = min(basic,greedy)
            return dp[l][r]
        return solve(0,n-1)    


17900