3144. Minimum Substring Partition of Equal Character Frequency LeetCode Solution

In this guide, you will get 3144. Minimum Substring Partition of Equal Character Frequency LeetCode Solution with the best time and space complexity. The solution to Minimum Substring Partition of Equal Character Frequency problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Substring Partition of Equal Character Frequency solution in C++
4. Minimum Substring Partition of Equal Character Frequency solution in Java
5. Minimum Substring Partition of Equal Character Frequency solution in Python
6. Additional Resources

Problem Statement of Minimum Substring Partition of Equal Character Frequency

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.

Complexity Analysis

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

3144. Minimum Substring Partition of Equal Character Frequency LeetCode Solution in C++

class Solution {
 public:
  int minimumSubstringsInPartition(string s) {
    const int n = s.length();
    // dp[i] := the minimum number of substrings in s[0..i]
    vector<int> dp(n, n);

    for (int i = 0; i < n; ++i) {
      vector<int> count(26);
      for (int j = i; j >= 0; --j) {
        ++count[s[j] - 'a'];
        if (isBalanced(count))  // word[j..i] is balanced.
          dp[i] = j > 0 ? min(dp[i], 1 + dp[j - 1]) : 1;
      }
    }

    return dp.back();
  }

 private:
  static constexpr int kMax = 1001;

  // Returns true if all non-zero frequencies are the same.
  bool isBalanced(const vector<int>& count) {
    int minfreq = kMax;
    int maxfreq = 0;
    for (const int freq : count)
      if (freq > 0) {
        minfreq = min(minfreq, freq);
        maxfreq = max(maxfreq, freq);
      }
    return minfreq == maxfreq;
  }
};
/* code provided by PROGIEZ */

3144. Minimum Substring Partition of Equal Character Frequency LeetCode Solution in Java

class Solution {
  public int minimumSubstringsInPartition(String s) {
    final int n = s.length();
    // dp[i] := the minimum number of substrings in s[0..i]
    int[] dp = new int[n];
    Arrays.fill(dp, n);

    for (int i = 0; i < n; ++i) {
      int[] count = new int[26];
      for (int j = i; j >= 0; --j) {
        ++count[s.charAt(j) - 'a'];
        if (isBalanced(count)) // word[j..i] is balanced.
          dp[i] = j > 0 ? Math.min(dp[i], 1 + dp[j - 1]) : 1;
      }
    }

    return dp[n - 1];
  }

  private static final int kMax = 1001;

  // Returns true if all non-zero frequencies are the same.
  private boolean isBalanced(int[] count) {
    int minfreq = kMax;
    int maxfreq = 0;
    for (final int freq : count)
      if (freq > 0) {
        minfreq = Math.min(minfreq, freq);
        maxfreq = Math.max(maxfreq, freq);
      }
    return minfreq == maxfreq;
  }
}
// code provided by PROGIEZ

3144. Minimum Substring Partition of Equal Character Frequency LeetCode Solution in Python

class Solution:
  def minimumSubstringsInPartition(self, s: str) -> int:
    n = len(s)
    # dp[i] := the minimum number of substrings in s[0..i]
    dp = [n] * n

    for i in range(n):
      count = collections.Counter()
      for j in range(i, -1, -1):
        count[s[j]] += 1
        # word[j..i] is balanced.
        if min(count.values()) == max(count.values()):
          dp[i] = min(dp[i], 1 + dp[j - 1] if j > 0 else 1)

    return dp[-1]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.