<p>Given a string <code>s</code>, you need to partition it into one or more <strong>balanced</strong> <span data-keyword="substring">substrings</span>. For example, if <code>s == &quot;ababcc&quot;</code> then <code>(&quot;abab&quot;, &quot;c&quot;, &quot;c&quot;)</code>, <code>(&quot;ab&quot;, &quot;abc&quot;, &quot;c&quot;)</code>, and <code>(&quot;ababcc&quot;)</code> are all valid partitions, but <code>(&quot;a&quot;, <strong>&quot;bab&quot;</strong>, &quot;cc&quot;)</code>, <code>(<strong>&quot;aba&quot;</strong>, &quot;bc&quot;, &quot;c&quot;)</code>, and <code>(&quot;ab&quot;, <strong>&quot;abcc&quot;</strong>)</code> are not. The unbalanced substrings are bolded.</p>

<p>Return the <strong>minimum</strong> number of substrings that you can partition <code>s</code> into.</p>

<p><strong>Note:</strong> A <strong>balanced</strong> string is a string where each character in the string occurs the same number of times.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;fabccddg&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>We can partition the string <code>s</code> into 3 substrings in one of the following ways: <code>(&quot;fab, &quot;ccdd&quot;, &quot;g&quot;)</code>, or <code>(&quot;fabc&quot;, &quot;cd&quot;, &quot;dg&quot;)</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;abababaccddb&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>We can partition the string <code>s</code> into 2 substrings like so: <code>(&quot;abab&quot;, &quot;abaccddb&quot;)</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists only of English lowercase letters.</li>
</ul>

class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        n = len(s)
        counts = [defaultdict(int) for _ in range(n)]
        counts[0][s[0]] = 1
        for i in range(1, n):
            counts[i] = counts[i-1].copy()
            counts[i][s[i]] += 1

        def are_all_same(dict1: defaultdict, dict2: defaultdict):
            prev = -1
            for key in dict2:
                delta = dict2[key] - dict1[key]
                if delta != prev and prev != -1 and delta != 0:
                    return False
                if delta != 0:
                    prev = delta
            return True

        dp = [[inf for _ in range(n)] for _ in range(n)]
        dp[0][0] = 1
        for i in range(1, n):
            dp[i][i] = 1
            dp[0][i] = 1 if are_all_same(defaultdict(int), counts[i]) else inf

        for i in range(1, n):
            for j in range(i+1, n):
                if are_all_same(counts[i- 1], counts[j]):
                    dp[i][j] = 1
        # print(dp)
        for i in range(1, n):
            if dp[0][i] == 1:
                continue
            for j in range(0, i):
                dp[0][i] = min(dp[0][i], dp[0][j] + dp[j+1][i])
        # print(dp)
        return dp[0][n-1]
26200