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)