<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:
        
        inf = float('inf')
        dp = [['i' for _ in range(len(s))] for _ in range(len(s))]
        min_col = [inf for _ in range(len(s))]

        start_cnt = [0 for _ in range(26)]
        another = defaultdict(int)

        for i in range(len(s)):
            curr_index = ord(s[i]) - 97
            old = start_cnt[curr_index]
            if old != 0:
                another[old] -= 1
                if not another[old]:
                    del another[old]
            start_cnt[curr_index] += 1
            another[start_cnt[curr_index]] += 1
            if len(another) == 1:
                dp[0][i] = 1
                min_col[i] = 1
        
        cnt = defaultdict(int)
        for i in range(1, len(s)):
            alpha = [0 for _ in range(26)]    
            dp[i][i] = min_col[i - 1] + 1
            alpha[ord(s[i]) - 97] += 1
            cnt[alpha[ord(s[i]) - 97]] += 1
            min_col[i] = min(min_col[i], dp[i][i])
            for j in range(i + 1, len(s)):
                curr_index = ord(s[j]) - 97
                old = alpha[curr_index]
                if old != 0:
                    cnt[old] -= 1
                    if not cnt[old]:
                        del cnt[old]
                alpha[curr_index] += 1
                cnt[alpha[curr_index]] += 1
                if len(cnt) == 1:
                    dp[i][j] = dp[i][i]
                    min_col[j] = min(min_col[j], dp[i][j])
            cnt.clear()
        
        return min_col[-1]
25200