Problem Description

Given a string s, you need to partition it into one or more balanced substrings. A balanced string is defined as a string where each character appears the same number of times.

For example, if s = "ababcc":

• Valid partitions include: ("abab", "c", "c"), ("ab", "abc", "c"), and ("ababcc")

  • In "abab": 'a' appears 2 times, 'b' appears 2 times (balanced)
  • In "c": 'c' appears 1 time (balanced)
  • In "abc": each character appears exactly 1 time (balanced)
  • In "ababcc": 'a' appears 2 times, 'b' appears 2 times, 'c' appears 2 times (balanced)

• Invalid partitions include: ("a", "bab", "cc"), ("aba", "bc", "c"), and ("ab", "abcc")

  • In "bab": 'b' appears 2 times, 'a' appears 1 time (not balanced)
  • In "aba": 'a' appears 2 times, 'b' appears 1 time (not balanced)
  • In "abcc": 'a' appears 1 time, 'b' appears 1 time, 'c' appears 2 times (not balanced)

The task is to find the minimum number of balanced substrings that you can partition the string s into. Each partition must cover the entire string without overlapping, and every substring in the partition must be balanced.

Intuition

The key insight is that this is an optimal partitioning problem where we need to make decisions about where to split the string. At each position, we face a choice: should we extend the current substring or start a new partition?

Think of it this way: starting from any position i in the string, we can try to form a balanced substring by extending it to various endpoints. For each valid balanced substring from position i to j, we can make a cut at position j+1 and then solve the remaining subproblem starting from j+1.

This naturally leads to a recursive approach with overlapping subproblems. If we define dfs(i) as the minimum number of partitions needed for the substring starting from index i to the end, then:

• For each possible endpoint j from i to n-1, we check if s[i:j+1] forms a balanced substring
• If it does, we have found one partition, and we need 1 + dfs(j+1) total partitions
• We take the minimum across all valid choices

The challenge is efficiently checking if a substring is balanced. A substring is balanced when all characters in it appear the same number of times - meaning if we track the frequency of each frequency value, we should have exactly one unique frequency.

For example, in "aabbcc", we have frequencies: a:2, b:2, c:2. All characters appear 2 times, so there's only one unique frequency value (2), making it balanced. In contrast, "aabc" has frequencies: a:2, b:1, c:1, with two different frequency values (1 and 2), so it's not balanced.

By maintaining two hash tables - one for character counts (cnt) and another for frequency of frequencies (freq) - we can efficiently update and check the balance condition as we extend our substring. When freq has size 1, all characters in the current substring appear the same number of times, indicating a balanced substring.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses memoized search (dynamic programming with recursion) combined with hash tables to efficiently find the minimum number of balanced partitions.

Implementation Details:

1. Main Recursive Function dfs(i):

   • Represents the minimum number of balanced substrings needed to partition s[i:] (from index i to the end)
   • Base case: If i >= n, return 0 (no more characters to process)
   • Uses @cache decorator for memoization to avoid recomputing the same subproblems

2. Two Hash Tables for Balance Checking:

   • cnt: Tracks the frequency of each character in the current substring
   • freq: Tracks how many characters have each frequency value

   For example, if substring is "aabbcc":

   • cnt = {'a': 2, 'b': 2, 'c': 2}
   • freq = {2: 3} (three characters appear 2 times each)

3. Iterative Extension Process:

   • For each starting position i, try all possible endpoints j from i to n-1
   • For each new character s[j] added to the current substring:
     • Update frequency tracking:
       • If cnt[s[j]] already exists, decrement freq[cnt[s[j]]]
       • If freq[cnt[s[j]]] becomes 0, remove it from freq
       • Increment cnt[s[j]]
       • Increment freq[cnt[s[j]]] (the new frequency count)
   • Check balance condition: If len(freq) == 1, the substring is balanced
     • This means all characters appear with the same frequency
     • Calculate the cost: 1 + dfs(j + 1) (one partition plus the minimum partitions for the rest)
     • Track the minimum cost across all valid endpoints

4. Optimization Strategy:

   • Initialize ans = n - i (worst case: each character forms its own partition)
   • Only update ans when finding a better solution: if t < ans: ans = t
   • The memoization ensures each state dfs(i) is computed only once

5. Final Answer:

   • Call dfs(0) to get the minimum partitions for the entire string

The time complexity is O(n²) for trying all possible substrings, with each substring taking O(1) amortized time to check balance using the frequency tables. The space complexity is O(n) for the recursion stack and memoization cache.

Example Walkthrough

Let's walk through the solution with s = "aabbcc".

Initial Setup:

• String: "aabbcc" (indices 0-5)
• We start with dfs(0) to find minimum partitions for the entire string

Step 1: dfs(0) - Starting from index 0

We'll try extending from index 0 to create balanced substrings:

• Try substring [0:1] = "a":

  • cnt = {'a': 1}, freq = {1: 1}
  • Balanced? Yes (only one frequency value)
  • Cost: 1 + dfs(1) (need to compute dfs(1))

• Try substring [0:2] = "aa":

  • cnt = {'a': 2}, freq = {2: 1}
  • Balanced? Yes
  • Cost: 1 + dfs(2) (need to compute dfs(2))

• Try substring [0:3] = "aab":

  • cnt = {'a': 2, 'b': 1}, freq = {2: 1, 1: 1}
  • Balanced? No (two different frequencies)
  • Skip this option

• Try substring [0:4] = "aabb":

  • cnt = {'a': 2, 'b': 2}, freq = {2: 2}
  • Balanced? Yes (both chars appear 2 times)
  • Cost: 1 + dfs(4) (need to compute dfs(4))

• Try substring [0:5] = "aabbc":

  • cnt = {'a': 2, 'b': 2, 'c': 1}, freq = {2: 2, 1: 1}
  • Balanced? No
  • Skip this option

• Try substring [0:6] = "aabbcc":

  • cnt = {'a': 2, 'b': 2, 'c': 2}, freq = {2: 3}
  • Balanced? Yes (all three chars appear 2 times)
  • Cost: 1 + dfs(6) = 1 + 0 = 1 (base case: dfs(6) = 0)

Step 2: Compute dfs(4) - Starting from index 4 ("cc")

• Try substring [4:5] = "c":

  • Balanced? Yes
  • Cost: 1 + dfs(5)

• Try substring [4:6] = "cc":

  • Balanced? Yes
  • Cost: 1 + dfs(6) = 1 + 0 = 1

So dfs(4) = 1

Step 3: Compute dfs(2) - Starting from index 2 ("bbcc")

• Try substring [2:3] = "b": Balanced, cost = 1 + dfs(3)
• Try substring [2:4] = "bb": Balanced, cost = 1 + dfs(4) = 1 + 1 = 2
• Try substring [2:6] = "bbcc": cnt = {'b': 2, 'c': 2}, Balanced, cost = 1 + 0 = 1

So dfs(2) = 1

Step 4: Compute dfs(1) - Starting from index 1 ("abbcc")

• Various attempts would show that the best option is likely partitioning into balanced substrings
• After checking all possibilities, dfs(1) = 2

Final Result: Going back to dfs(0):

• Option 1: "a" + rest → 1 + dfs(1) = 1 + 2 = 3
• Option 2: "aa" + rest → 1 + dfs(2) = 1 + 1 = 2
• Option 3: "aabb" + rest → 1 + dfs(4) = 1 + 1 = 2
• Option 4: "aabbcc" → 1 + dfs(6) = 1 + 0 = 1

The minimum is 1, achieved by taking the entire string as one balanced partition.

This demonstrates how the algorithm:

1. Explores all possible balanced substrings starting from each position
2. Uses memoization to avoid recomputing subproblems
3. Tracks character frequencies efficiently using two hash tables
4. Finds the optimal partition by choosing the minimum cost at each step

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses dynamic programming with memoization. The dfs(i) function is called for each starting position from 0 to n-1, resulting in at most n unique states. For each state dfs(i), the function iterates through all possible ending positions from i to n-1, which takes O(n-i) time. Within each iteration, the operations on the cnt and freq dictionaries take O(1) time since we're dealing with at most 26 distinct characters. Therefore, the total time complexity is:

• Sum from i=0 to n-1 of (n-i) = n + (n-1) + ... + 1 = n(n+1)/2 = O(n²)

Space Complexity: O(n × |Σ|)

The space complexity consists of:

1. Memoization cache: The @cache decorator stores results for each unique starting position i, requiring O(n) space for the cached return values.
2. Recursion stack: The maximum recursion depth is O(n) in the worst case when each character forms its own partition.
3. Local variables per recursive call: Each call maintains:
   • cnt dictionary: stores character counts, at most |Σ| = 26 entries
   • freq dictionary: stores frequency counts, at most |Σ| = 26 entries

Since the recursion depth can be O(n) and each level maintains dictionaries of size O(|Σ|), the total space complexity is O(n × |Σ|), where |Σ| = 26 for lowercase English letters.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Balance Check - Using Character Count Instead of Frequency Uniformity

A common mistake is checking if a substring is balanced by only looking at character counts directly, rather than verifying all characters have the same count.

Incorrect approach:

# WRONG: Just checking if counts exist
if len(char_count) > 0:  # This doesn't ensure balance!
    partitions = 1 + dfs(end_index + 1)

Why it fails: For substring "aabbc", char_count = {'a': 2, 'b': 2, 'c': 1}. The substring is NOT balanced because 'c' appears 1 time while others appear 2 times.

Correct approach:

# RIGHT: Check if all characters have the same frequency
if len(count_frequency) == 1:  # All chars appear same number of times
    partitions = 1 + dfs(end_index + 1)

2. Forgetting to Update Frequency Map When Character Count Changes

When adding a character to the current substring, its count changes. You must remove the old frequency before adding the new one.

Incorrect approach:

# WRONG: Only adding new frequency without removing old
char_count[current_char] += 1
count_frequency[char_count[current_char]] += 1  # Old frequency still exists!

Why it fails: If 'a' had count 2 and becomes 3, count_frequency would incorrectly show both {2: 1, 3: 1} instead of just {3: 1}.

Correct approach:

# RIGHT: Remove old frequency first, then add new
if char_count[current_char] > 0:
    count_frequency[char_count[current_char]] -= 1
    if count_frequency[char_count[current_char]] == 0:
        del count_frequency[char_count[current_char]]

char_count[current_char] += 1
count_frequency[char_count[current_char]] += 1

3. Not Cleaning Up Zero-Frequency Entries

Leaving zero-valued entries in count_frequency will break the balance check.

Incorrect approach:

# WRONG: Leaving zero entries in frequency map
count_frequency[char_count[current_char]] -= 1
# Not removing when it becomes 0!

Why it fails: With count_frequency = {2: 0, 3: 2}, len(count_frequency) returns 2, incorrectly indicating imbalance when all characters actually appear 3 times.

Correct approach:

# RIGHT: Remove zero entries
count_frequency[char_count[current_char]] -= 1
if count_frequency[char_count[current_char]] == 0:
    del count_frequency[char_count[current_char]]

4. Resetting Data Structures Outside the Loop

Creating char_count and count_frequency outside the inner loop causes them to accumulate data incorrectly across different substring attempts.

Incorrect approach:

def dfs(start_index):
    char_count = defaultdict(int)
    count_frequency = defaultdict(int)
  
    for end_index in range(start_index, string_length):
        # char_count keeps accumulating even when trying different partitions!

Correct approach:

def dfs(start_index):
    # Fresh data structures for each starting position
    char_count = defaultdict(int)
    count_frequency = defaultdict(int)
  
    for end_index in range(start_index, string_length):
        # Builds substring incrementally from start_index