<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:
        s = "".join(char for char, _ in itertools.groupby(s))
        n = len(s)

        # min_turns[i][j] represents the minimum number of turns to print s[i] to s[j]
        min_turns = [[0] * n for _ in range(n)]

        # Initialize base case
        for i in range(n):
            # It takes 1 turn to print a single character
            min_turns[i][i] = 1

        # Fill the dp table
        for length in range(2, n + 1):
            for start in range(n - length + 1):
                end = start + length - 1

                # Initialize with worst case: print each character separately
                min_turns[start][end] = length

                # Try all possible splits and find the minimum
                for split in range(length - 1):
                    total_turns = (
                        min_turns[start][start + split]
                        + min_turns[start + split + 1][end]
                    )

                    # If the characters at the split and end match, we can save one turn
                    if s[start + split] == s[end]:
                        total_turns -= 1

                    min_turns[start][end] = min(
                        min_turns[start][end], total_turns
                    )

        # Return the minimum turns needed to print the entire string
        return min_turns[0][n - 1] if n > 0 else 0
16000