Link to Question

MEDIUM

Minimum Substring Partition of Equal Character Frequency

You are given a string s. Partition s into one or more substrings such that the frequency of each character in each substring is the same.

Return the minimum number of substrings in such a partition.

Example

Input:

s = "fabccddg"

Output:

3

Explanation: One optimal partition is ["fab", "ccdd", "g"]. - In "fab", all characters appear once. - In "ccdd", both 'c' and 'd' appear twice. - In "g", 'g' appears once.

---

Constraints

• 1 ≤ s.length ≤ 1000
• s consists only of lowercase English letters.

---

Solution: Dynamic Programming

• Time Complexity: O(n^2)
• Space Complexity: O(n)

C++

class Solution {
public:
    bool check(vector<int>& c) {
        int temp = -1;
        for(auto v : c) {
            if (v != 0) {
                if (temp == -1) temp = v;
                else if (temp != v) return false;
            }
        }
        return true;
    }

    int minimumSubstringsInPartition(string s) {
        int n = s.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            vector<int> count(26, 0);
            for (int j = i; j >= 0; j--) {
                count[s[i]-'a']++;
                if (check(count))
                    dp[i+1] = min(dp[i+1], dp[j]+1); 
            }
        }
        return dp.back();
    }
};