Skip to content

3144. Minimum Substring Partition of Equal Character Frequency

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.

Solutions

Solution 1: Memoized Search + Hash Table

Thinking

\(s\) must be split into as few balanced pieces as possible, each with equal character frequencies. Full partitions are exponential; \(n\le 1000\) allows quadratic DP.

From index \(i\), extending \(j\) can test balance with frequency maps: a piece is legal when only one frequency remains. The optimum depends only on the start index.

Memoize \(dfs(i)\): maintain \(cnt\) and \(freq\), and when \(freq\) has size \(1\) take \(1+dfs(j+1)\). The empty suffix returns \(0\).

We design a function \(\textit{dfs}(i)\), which represents the minimum number of substrings starting from \(s[i]\). The answer is \(\textit{dfs}(0)\).

The calculation process of the function \(\textit{dfs}(i)\) is as follows:

If \(i \geq n\), it means all characters have been processed, so return \(0\).

Otherwise, we maintain a hash table \(\textit{cnt}\) to represent the frequency of each character in the current substring. Additionally, we maintain a hash table \(\textit{freq}\) to represent the frequency of each character's occurrence count.

Then we enumerate \(j\) from \(i\) to \(n-1\), representing the end position of the current substring. For each \(j\), we update \(\textit{cnt}\) and \(\textit{freq}\), then check if the size of \(\textit{freq}\) is \(1\). If it is, we can split from \(j+1\), and the answer is \(1 + \textit{dfs}(j+1)\). We take the minimum answer among all \(j\) as the return value of the function.

To avoid repeated calculations, we use memoized search.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n \times |\Sigma|)\). Here, \(n\) is the length of the string \(s\), and \(|\Sigma|\) represents the size of the character set, which is \(26\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            cnt = defaultdict(int)
            freq = defaultdict(int)
            ans = n - i
            for j in range(i, n):
                if cnt[s[j]]:
                    freq[cnt[s[j]]] -= 1
                    if not freq[cnt[s[j]]]:
                        freq.pop(cnt[s[j]])
                cnt[s[j]] += 1
                freq[cnt[s[j]]] += 1
                if len(freq) == 1 and (t := 1 + dfs(j + 1)) < ans:
                    ans = t
            return ans

        n = len(s)
        return dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private int n;
    private char[] s;
    private Integer[] f;

    public int minimumSubstringsInPartition(String s) {
        n = s.length();
        f = new Integer[n];
        this.s = s.toCharArray();
        return dfs(0);
    }

    private int dfs(int i) {
        if (i >= n) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        int[] cnt = new int[26];
        Map<Integer, Integer> freq = new HashMap<>(26);
        int ans = n - i;
        for (int j = i; j < n; ++j) {
            int k = s[j] - 'a';
            if (cnt[k] > 0) {
                if (freq.merge(cnt[k], -1, Integer::sum) == 0) {
                    freq.remove(cnt[k]);
                }
            }
            ++cnt[k];
            freq.merge(cnt[k], 1, Integer::sum);
            if (freq.size() == 1) {
                ans = Math.min(ans, 1 + dfs(j + 1));
            }
        }
        return f[i] = ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minimumSubstringsInPartition(string s) {
        int n = s.size();
        int f[n];
        memset(f, -1, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i >= n) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }
            f[i] = n - i;
            int cnt[26]{};
            unordered_map<int, int> freq;
            for (int j = i; j < n; ++j) {
                int k = s[j] - 'a';
                if (cnt[k]) {
                    freq[cnt[k]]--;
                    if (freq[cnt[k]] == 0) {
                        freq.erase(cnt[k]);
                    }
                }
                ++cnt[k];
                ++freq[cnt[k]];
                if (freq.size() == 1) {
                    f[i] = min(f[i], 1 + dfs(j + 1));
                }
            }
            return f[i];
        };
        return dfs(0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func minimumSubstringsInPartition(s string) int {
    n := len(s)
    f := make([]int, n)
    for i := range f {
        f[i] = -1
    }
    var dfs func(int) int
    dfs = func(i int) int {
        if i >= n {
            return 0
        }
        if f[i] != -1 {
            return f[i]
        }
        cnt := [26]int{}
        freq := map[int]int{}
        f[i] = n - i
        for j := i; j < n; j++ {
            k := int(s[j] - 'a')
            if cnt[k] > 0 {
                freq[cnt[k]]--
                if freq[cnt[k]] == 0 {
                    delete(freq, cnt[k])
                }
            }
            cnt[k]++
            freq[cnt[k]]++
            if len(freq) == 1 {
                f[i] = min(f[i], 1+dfs(j+1))
            }
        }
        return f[i]
    }
    return dfs(0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function minimumSubstringsInPartition(s: string): number {
    const n = s.length;
    const f: number[] = Array(n).fill(-1);
    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        const cnt: Map<number, number> = new Map();
        const freq: Map<number, number> = new Map();
        f[i] = n - i;
        for (let j = i; j < n; ++j) {
            const k = s.charCodeAt(j) - 97;
            if (freq.has(cnt.get(k)!)) {
                freq.set(cnt.get(k)!, freq.get(cnt.get(k)!)! - 1);
                if (freq.get(cnt.get(k)!) === 0) {
                    freq.delete(cnt.get(k)!);
                }
            }
            cnt.set(k, (cnt.get(k) || 0) + 1);
            freq.set(cnt.get(k)!, (freq.get(cnt.get(k)!) || 0) + 1);
            if (freq.size === 1) {
                f[i] = Math.min(f[i], 1 + dfs(j + 1));
            }
        }
        return f[i];
    };
    return dfs(0);
}

Solution 2: Memoized Search (Optimization)

Thinking

Method 1 keeps a second map of frequency-of-frequencies, which adds constants and fiddly updates.

Balance is equivalent to length equaling (maximum frequency) times (number of distinct letters). Only \(cnt\) and that maximum \(m\) are required.

While extending \(j\), update \(m\) and recurse when \(j-i+1=m\cdot|cnt|\). The state is still the start index, with a shorter inner loop.

We can optimize Solution 1 by not maintaining the \(\textit{freq}\) hash table. Instead, we only need to maintain a hash table \(\textit{cnt}\), which represents the frequency of each character in the current substring. Additionally, we maintain two variables \(k\) and \(m\) to represent the number of distinct characters in the current substring and the maximum frequency of any character, respectively. For a substring \(s[i..j]\), if \(j-i+1 = m \times k\), then this substring is a balanced substring.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n \times |\Sigma|)\). Here, \(n\) is the length of the string \(s\), and \(|\Sigma|\) represents the size of the character set, which is \(26\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            cnt = defaultdict(int)
            m = 0
            ans = n - i
            for j in range(i, n):
                cnt[s[j]] += 1
                m = max(m, cnt[s[j]])
                if j - i + 1 == m * len(cnt):
                    ans = min(ans, 1 + dfs(j + 1))
            return ans

        n = len(s)
        ans = dfs(0)
        dfs.cache_clear()
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private int n;
    private char[] s;
    private Integer[] f;

    public int minimumSubstringsInPartition(String s) {
        n = s.length();
        f = new Integer[n];
        this.s = s.toCharArray();
        return dfs(0);
    }

    private int dfs(int i) {
        if (i >= n) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        int[] cnt = new int[26];
        int ans = n - i;
        int k = 0, m = 0;
        for (int j = i; j < n; ++j) {
            k += ++cnt[s[j] - 'a'] == 1 ? 1 : 0;
            m = Math.max(m, cnt[s[j] - 'a']);
            if (j - i + 1 == k * m) {
                ans = Math.min(ans, 1 + dfs(j + 1));
            }
        }
        return f[i] = ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minimumSubstringsInPartition(string s) {
        int n = s.size();
        int f[n];
        memset(f, -1, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i >= n) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }
            f[i] = n - i;
            int cnt[26]{};
            int k = 0, m = 0;
            for (int j = i; j < n; ++j) {
                k += ++cnt[s[j] - 'a'] == 1 ? 1 : 0;
                m = max(m, cnt[s[j] - 'a']);
                if (j - i + 1 == k * m) {
                    f[i] = min(f[i], 1 + dfs(j + 1));
                }
            }
            return f[i];
        };
        return dfs(0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func minimumSubstringsInPartition(s string) int {
    n := len(s)
    f := make([]int, n)
    for i := range f {
        f[i] = -1
    }
    var dfs func(int) int
    dfs = func(i int) int {
        if i >= n {
            return 0
        }
        if f[i] != -1 {
            return f[i]
        }
        cnt := [26]int{}
        f[i] = n - i
        k, m := 0, 0
        for j := i; j < n; j++ {
            x := int(s[j] - 'a')
            cnt[x]++
            if cnt[x] == 1 {
                k++
            }
            m = max(m, cnt[x])
            if j-i+1 == k*m {
                f[i] = min(f[i], 1+dfs(j+1))
            }
        }
        return f[i]
    }
    return dfs(0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function minimumSubstringsInPartition(s: string): number {
    const n = s.length;
    const f: number[] = Array(n).fill(-1);
    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        const cnt: number[] = Array(26).fill(0);
        f[i] = n - i;
        let [k, m] = [0, 0];
        for (let j = i; j < n; ++j) {
            const x = s.charCodeAt(j) - 97;
            k += ++cnt[x] === 1 ? 1 : 0;
            m = Math.max(m, cnt[x]);
            if (j - i + 1 === k * m) {
                f[i] = Math.min(f[i], 1 + dfs(j + 1));
            }
        }
        return f[i];
    };
    return dfs(0);
}

Solution 3: Dynamic Programming

Thinking

Memoization still pays recursion and cache overhead. The same transition has no aftereffect.

Let \(f[i]\) be the fewest pieces for the prefix of length \(i\). For each right end \(i\), expand left to \(j\) and relax \(f[i+1]\) with \(f[j]+1\) when the piece is balanced.

The table yields \(f[n]\), using linear DP memory plus one count map.

We can convert the memoized search into dynamic programming. Define the state \(f[i]\) as the minimum number of substrings required to partition the first \(i\) characters. Initially, \(f[0] = 0\), and the rest \(f[i] = +\infty\) or \(f[i] = n\).

Next, we enumerate \(i\) from \(0\) to \(n-1\). For each \(i\), we maintain a hash table \(\textit{cnt}\) to represent the frequency of each character in the current substring. Additionally, we maintain two variables \(k\) and \(m\) to represent the number of distinct characters in the current substring and the maximum frequency of any character, respectively. For a substring \(s[j..i]\), if \(i-j+1 = m \times k\), then this substring is a balanced substring. At this point, we can partition from \(j\), so \(f[i+1] = \min(f[i+1], f[j] + 1)\).

The final answer is \(f[n]\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n + |\Sigma|)\). Here, \(n\) is the length of the string \(s\), and \(|\Sigma|\) represents the size of the character set, which is \(26\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        n = len(s)
        f = [inf] * (n + 1)
        f[0] = 0
        for i in range(n):
            cnt = defaultdict(int)
            m = 0
            for j in range(i, -1, -1):
                cnt[s[j]] += 1
                m = max(m, cnt[s[j]])
                if i - j + 1 == len(cnt) * m:
                    f[i + 1] = min(f[i + 1], f[j] + 1)
        return f[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        Arrays.fill(f, n);
        f[0] = 0;
        for (int i = 0; i < n; ++i) {
            int[] cnt = new int[26];
            int k = 0, m = 0;
            for (int j = i; j >= 0; --j) {
                k += ++cnt[cs[j] - 'a'] == 1 ? 1 : 0;
                m = Math.max(m, cnt[cs[j] - 'a']);
                if (i - j + 1 == k * m) {
                    f[i + 1] = Math.min(f[i + 1], 1 + f[j]);
                }
            }
        }
        return f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumSubstringsInPartition(string s) {
        int n = s.size();
        vector<int> f(n + 1, n);
        f[0] = 0;
        for (int i = 0; i < n; ++i) {
            int cnt[26]{};
            int k = 0, m = 0;
            for (int j = i; ~j; --j) {
                k += ++cnt[s[j] - 'a'] == 1;
                m = max(m, cnt[s[j] - 'a']);
                if (i - j + 1 == k * m) {
                    f[i + 1] = min(f[i + 1], f[j] + 1);
                }
            }
        }
        return f[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func minimumSubstringsInPartition(s string) int {
    n := len(s)
    f := make([]int, n+1)
    for i := range f {
        f[i] = n
    }
    f[0] = 0
    for i := 0; i < n; i++ {
        cnt := [26]int{}
        k, m := 0, 0
        for j := i; j >= 0; j-- {
            x := int(s[j] - 'a')
            cnt[x]++
            if cnt[x] == 1 {
                k++
            }
            m = max(m, cnt[x])
            if i-j+1 == k*m {
                f[i+1] = min(f[i+1], 1+f[j])
            }
        }
    }
    return f[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function minimumSubstringsInPartition(s: string): number {
    const n = s.length;
    const f: number[] = Array(n + 1).fill(n);
    f[0] = 0;
    for (let i = 0; i < n; ++i) {
        const cnt: number[] = Array(26).fill(0);
        let [k, m] = [0, 0];
        for (let j = i; ~j; --j) {
            const x = s.charCodeAt(j) - 97;
            k += ++cnt[x] === 1 ? 1 : 0;
            m = Math.max(m, cnt[x]);
            if (i - j + 1 === k * m) {
                f[i + 1] = Math.min(f[i + 1], 1 + f[j]);
            }
        }
    }
    return f[n];
}

Comments