3144. Minimum Substring Partition of Equal Character Frequency

Problem Link

Description

---

Given a string s, you need to partition it into one or more balanced substrings. For example, if s == "ababcc" then ("abab", "c", "c"), ("ab", "abc", "c"), and ("ababcc") are all valid partitions, but ("a", "bab", "cc"), ("aba", "bc", "c"), and ("ab", "abcc") are not. The unbalanced substrings are bolded.

Return the minimum number of substrings that you can partition s into.

Note: A balanced string is a string where each character in the string occurs the same number of times.

 

Example 1:

Input: s = "fabccddg"

Output: 3

Explanation:

We can partition the string s into 3 substrings in one of the following ways: ("fab, "ccdd", "g"), or ("fabc", "cd", "dg").

Example 2:

Input: s = "abababaccddb"

Output: 2

Explanation:

We can partition the string s into 2 substrings like so: ("abab", "abaccddb").

 

Constraints:

• 1 <= s.length <= 1000
• s consists only of English lowercase letters.

Solution

---

Python3

class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        N = len(s)
        
        @cache
        def go(index):
            if index == N: return 0
            
            res = inf
            counter = [0] * 26
            
            for i in range(index, N):
                c = ord(s[i]) - ord('a')
                counter[c] += 1
                ok = True
                
                for k in range(26):
                    if counter[k] == 0: continue
                    
                    if counter[k] != counter[c]:
                        ok = False
                        break
                
                if ok:
                    res = min(res, 1 + go(i + 1))
            
            return res
        
        return go(0)