We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Substring Partition of Equal Character Frequency

Number: 3403

Difficulty: Medium

Paid? No

Companies: Amazon, Mitsogo

Problem Description

Given a string s, partition it into one or more substrings such that each substring is balanced. A balanced substring is defined as one in which every character present appears the same number of times. For example, while "aabb" is balanced (each character appears twice), "aabbc" is not balanced. The goal is to determine the minimum number of balanced substrings the string can be split into.

Key Insights

  • Every single character is balanced on its own.
  • A substring is balanced if all its nonzero character frequencies are equal.
  • We can use a dynamic programming approach where dp[i] represents the minimum number of balanced substrings for the prefix ending at index i-1.
  • We can incrementally build candidate substrings by expanding the window and checking if the substring remains balanced (using a fixed character frequency array of size 26).
  • The overall time complexity is acceptable since checking balance for a candidate substring takes constant time (O(26)).

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n) (for the dp array, with constant space for frequency arrays)

Solution

We solve the problem using dynamic programming. First, we initialize a dp array where dp[i] is the minimum number of balanced substrings for s[0:i]. We then iterate over every possible starting index i. For each i, we use an inner loop to expand the candidate substring s[i:j+1] while maintaining a frequency count for the 26 lowercase letters. At every step, we check if the nonzero frequencies in the current substring are all equal. If they are, we update dp[j+1] to be the minimum of itself and dp[i] + 1. In the end, dp[n] will hold the minimum number of balanced substrings for the entire string.

The trick lies in efficiently checking substring balance by updating the frequency count in the inner loop and checking all 26 positions, which is a constant operation.

Code Solutions

# Function to determine the minimum number of balanced substrings of s
def minBalancedSubstringPartition(s: str) -> int:
    n = len(s)
    # dp[i] stores the minimum number of balanced substrings for s[0:i]
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # base case: empty string needs 0 partitions
    
    # iterate over every possible starting index i
    for i in range(n):
        counts = [0] * 26  # frequency count for each letter
        # expand the substring from index i to j
        for j in range(i, n):
            # update the count for current character
            counts[ord(s[j]) - ord('a')] += 1
            freq = 0
            valid = True
            # check if the current substring is balanced
            for count in counts:
                if count > 0:
                    if freq == 0:
                        freq = count
                    elif count != freq:
                        valid = False
                        break
            # if balanced, update dp for substring ending at j+1
            if valid:
                dp[j + 1] = min(dp[j + 1], dp[i] + 1)
    return dp[n]

# Example usage:
if __name__ == "__main__":
    s = "fabccddg"
    print(minBalancedSubstringPartition(s))  # Output should be 3
← Back to All Questions