Minimum Substring Partition of Equal Character Frequency Solution
Minimum Substring Partition of Equal Character Frequency solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Substring Partition of Equal Character Frequency is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Dynamic Programming, Counting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is balanced if every character that appears in it appears the same number of times. For example "aabb", "abc" and "zzz" are balanced, while "aab" is not.
Given a string s, split it into one or more balanced substrings (contiguous, covering s in order). For example "ababcc" can be split as ("abab", "c", "c") or ("ab", "abc", "c"), but ("a", "bab", "cc") is not valid because "bab" is unbalanced.
Return the minimum number of substrings in such a split.
Example 1
Input: s = "fabccddg"
Output: 3
Explanation: One optimal split is ("fab", "ccdd", "g").
Example 2
Input: s = "abababaccddb"
Output: 2
Explanation: ("abab", "abaccddb"): the second piece has two of each of a, b, c, d.
Example 3
Input: s = "a"
Output: 1
Constraints
1 <= s.length <= 1000s consists only of lowercase English letters
Hints for Minimum Substring Partition of Equal Character Frequency
Hint 1
This is a partition DP:
dp[i]= fewest balanced pieces covering the firsticharacters.Hint 2
For a fixed end
i, grow the last piece leftwards one character at a time and keep its letter counts up to date, instead of recounting every substring.Hint 3
A piece is balanced exactly when
(largest count) × (number of distinct letters) == length. Track both while extending, and each check is O(1).
How to solve Minimum Substring Partition of Equal Character Frequency
Classic minimum partition DP. The only question is how to test each candidate last piece quickly: grow it from right to left, maintaining its letter counts, its number of distinct letters and its maximum count.
Approach
dp[0] = 0; every other entry starts at infinity.- For each end
ifrom 1 ton, reset the counts and walkjfromi - 1down to 0, addings[j]to the pieces[j..i-1]. Updatedistinctwhen a count goes from 0 to 1, andmaxCount. - If
maxCount · distinct == i - j, the piece is balanced:dp[i] = min(dp[i], dp[j] + 1). - Return
dp[n].
Why it works
If every present letter appears exactly maxCount times, the length is maxCount · distinct. Conversely, if any letter appears fewer times, the length is strictly smaller than that product. So the product test is equivalent to balance. The DP tries every possible last piece, so the minimum is exact.
Complexity
- Time —
O(n^2) - Space —
O(n + 26)
Pitfalls
- A single character is always balanced, so
dp[i] ≤ dp[i-1] + 1and the answer is at mostn. - Recomputing all 26 counts for each substring works but is 26 times slower; the product test avoids it.
- A greedy that takes the longest balanced prefix each time is not optimal.
Reference solution
Python
def minimumSubstringsInPartition(s: str) -> int:
n = len(s)
dp = [0] + [n + 1] * n
for i in range(1, n + 1):
cnt = [0] * 26
distinct = 0
mx = 0
for j in range(i - 1, -1, -1):
c = ord(s[j]) - 97
if cnt[c] == 0:
distinct += 1
cnt[c] += 1
if cnt[c] > mx:
mx = cnt[c]
if mx * distinct == i - j and dp[j] + 1 < dp[i]:
dp[i] = dp[j] + 1
return dp[n]Java
public static int minimumSubstringsInPartition(String s) {
int n = s.length();
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int[] cnt = new int[26];
int distinct = 0, mx = 0;
for (int j = i - 1; j >= 0; j--) {
int c = s.charAt(j) - 'a';
if (cnt[c]++ == 0) distinct++;
mx = Math.max(mx, cnt[c]);
if (mx * distinct == i - j) dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
return dp[n];
}C++
int minimumSubstringsInPartition(string s) {
int n = s.size();
vector<int> dp(n + 1, n + 1);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int cnt[26] = {0};
int distinct = 0, mx = 0;
for (int j = i - 1; j >= 0; j--) {
int c = s[j] - 'a';
if (cnt[c]++ == 0) distinct++;
mx = max(mx, cnt[c]);
if (mx * distinct == i - j) dp[i] = min(dp[i], dp[j] + 1);
}
}
return dp[n];
}JavaScript
var minimumSubstringsInPartition = function(s) {
var n = s.length;
var dp = new Array(n + 1).fill(n + 1);
dp[0] = 0;
for (var i = 1; i <= n; i++) {
var cnt = new Array(26).fill(0), distinct = 0, mx = 0;
for (var j = i - 1; j >= 0; j--) {
var c = s.charCodeAt(j) - 97;
if (cnt[c] === 0) distinct++;
cnt[c]++;
if (cnt[c] > mx) mx = cnt[c];
if (mx * distinct === i - j && dp[j] + 1 < dp[i]) dp[i] = dp[j] + 1;
}
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets