Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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

Method 1 – Greedy Partitioning

Intuition

We can greedily partition the string whenever the current substring can be balanced. For each substring, we count character frequencies and check if all nonzero counts are equal.

Approach

  1. Initialize count = 0, i = 0.
  2. While i < n, try all possible substrings s[i:j] for j > i.
  3. For each substring, count character frequencies and check if all nonzero counts are equal.
  4. If balanced, increment count and move i to j.
  5. Repeat until end of string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int minimumPartition(string s) {
        int n = s.size(), ans = 0, i = 0;
        while (i < n) {
            vector<int> freq(26, 0);
            for (int j = i; j < n; ++j) {
                freq[s[j]-'a']++;
                int cnt = 0, val = 0;
                for (int f : freq) if (f) { if (!val) val = f; if (f != val) { val = -1; break; } cnt++; }
                if (val > 0) { ans++; i = j+1; break; }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func minimumPartition(s string) int {
    n, ans, i := len(s), 0, 0
    for i < n {
        freq := make([]int, 26)
        for j := i; j < n; j++ {
            freq[s[j]-'a']++
            cnt, val := 0, 0
            for _, f := range freq {
                if f > 0 {
                    if val == 0 { val = f }
                    if f != val { val = -1; break }
                    cnt++
                }
            }
            if val > 0 {
                ans++; i = j+1; break
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int minimumPartition(String s) {
        int n = s.length(), ans = 0, i = 0;
        while (i < n) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j)-'a']++;
                int cnt = 0, val = 0;
                for (int f : freq) if (f > 0) { if (val == 0) val = f; if (f != val) { val = -1; break; } cnt++; }
                if (val > 0) { ans++; i = j+1; break; }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minimumPartition(s: String): Int {
        val n = s.length
        var ans = 0; var i = 0
        while (i < n) {
            val freq = IntArray(26)
            for (j in i until n) {
                freq[s[j]-'a']++
                var cnt = 0; var val_ = 0
                for (f in freq) if (f > 0) { if (val_ == 0) val_ = f; if (f != val_) { val_ = -1; break }; cnt++ }
                if (val_ > 0) { ans++; i = j+1; break }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minimumPartition(self, s: str) -> int:
        n, ans, i = len(s), 0, 0
        while i < n:
            freq = [0]*26
            for j in range(i, n):
                freq[ord(s[j])-97] += 1
                vals = [f for f in freq if f]
                if len(set(vals)) == 1:
                    ans += 1
                    i = j+1
                    break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn minimum_partition(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = 0; let mut i = 0;
        while i < n {
            let mut freq = [0;26];
            for j in i..n {
                freq[(s[j]-b'a') as usize] += 1;
                let vals: Vec<_> = freq.iter().filter(|&&f| f>0).collect();
                if vals.iter().all(|&f| *f == *vals[0]) {
                    ans += 1; i = j+1; break;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minimumPartition(s: string): number {
        const n = s.length;
        let ans = 0, i = 0;
        while (i < n) {
            const freq = Array(26).fill(0);
            for (let j = i; j < n; j++) {
                freq[s.charCodeAt(j)-97]++;
                const vals = freq.filter(f=>f);
                if (new Set(vals).size === 1) {
                    ans++; i = j+1; break;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * 26) — For each start, try all ends and check frequencies.
  • 🧺 Space complexity: O(26) — For frequency array.