Minimum Substring Partition of Equal Character Frequency

Medium
1654.

Minimum Substring Partition of Equal Character Frequency

Minimum Substring Partition of Equal Character Frequency is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon interviews.

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 <= 1000
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minimumSubstringsInPartition = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • s consists only of lowercase English letters

Hints for Minimum Substring Partition of Equal Character Frequency

  1. Hint 1

    This is a partition DP: dp[i] = fewest balanced pieces covering the first i characters.

  2. 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.

  3. 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

  1. dp[0] = 0; every other entry starts at infinity.
  2. For each end i from 1 to n, reset the counts and walk j from i - 1 down to 0, adding s[j] to the piece s[j..i-1]. Update distinct when a count goes from 0 to 1, and maxCount.
  3. If maxCount · distinct == i - j, the piece is balanced: dp[i] = min(dp[i], dp[j] + 1).
  4. 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] + 1 and the answer is at most n.
  • 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