LeetCode 3343 - Count Number of Balanced Permutations

We are given a string num consisting only of digits. We may rearrange the digits in any possible way, but we only count distinct permutations. A permutation is considered balanced if the sum of the digits placed at even indices equals the sum of the digits placed at odd indices.

leetcodehardmathstringdynamic-programmingcombinatorics

LeetCode Problem 3343

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming, Combinatorics

Solution

Problem Understanding

We are given a string num consisting only of digits. We may rearrange the digits in any possible way, but we only count distinct permutations. A permutation is considered balanced if the sum of the digits placed at even indices equals the sum of the digits placed at odd indices.

The indices are zero based. That means:

  • Even indices are 0, 2, 4, ...
  • Odd indices are 1, 3, 5, ...

For example, in the string "132":

  • Even indices contain 1 and 2, sum = 3
  • Odd indices contain 3, sum = 3

So "132" is balanced.

The task is to count how many distinct permutations of the given digits satisfy this condition. Since the number of permutations can become extremely large, we return the answer modulo:

$$10^9 + 7$$

The length of the string can be as large as 80, which immediately tells us that generating permutations explicitly is impossible. Even for length 20, the number of permutations is already astronomically large.

An important observation is that balanced permutations depend only on:

  • How many positions are even
  • How many positions are odd
  • Which digits are assigned to those positions

The exact arrangement inside even or odd positions matters only combinatorially.

Several edge cases are important:

  • If the total digit sum is odd, no balanced permutation can exist because the two sides must sum to the same value.
  • Duplicate digits must not be overcounted.
  • Strings containing many repeated digits such as "000000" can easily break naive permutation counting.
  • Odd length strings have one more even index than odd indices because indexing starts at 0.

For a string of length n:

  • Number of even positions:

$$\left\lceil \frac{n}{2} \right\rceil$$

  • Number of odd positions:

$$\left\lfloor \frac{n}{2} \right\rfloor$$

The problem asks us to count distinct assignments of digits into these position groups such that the sums match.

Approaches

Brute Force Approach

The brute force solution generates every distinct permutation of the string and checks whether it is balanced.

To verify balance, we iterate through the permutation:

  • Add digits at even indices to one sum
  • Add digits at odd indices to another sum

If the sums are equal, we increment the answer.

This approach is correct because it explicitly examines every valid permutation and directly checks the required property.

However, the complexity is completely infeasible.

If all digits are unique and the length is 80, the number of permutations is:

$$80!$$

which is far beyond computable limits.

Even using pruning or duplicate elimination does not help enough.

Optimal Approach

The key insight is that we do not actually care about the order of digits initially. We only care about how many copies of each digit are placed into even positions and odd positions.

Suppose:

  • evenCount = number of even indices
  • oddCount = number of odd indices
  • Total digit sum = S

For a balanced permutation to exist:

$$S \text{ must be even}$$

because both sides must equal:

$$\frac{S}{2}$$

Now consider each digit independently.

If digit d appears cnt[d] times, we decide:

  • x copies go to even positions
  • cnt[d] - x copies go to odd positions

The total contribution to the even-index sum becomes:

$$\sum d \cdot x_d$$

and this must equal S / 2.

This becomes a combinatorial dynamic programming problem.

For each valid distribution of digits:

  • Number of ways to arrange digits in even positions:

$$\frac{evenCount!}{\prod x_d!}$$

  • Number of ways to arrange digits in odd positions:

$$\frac{oddCount!}{\prod (cnt[d]-x_d)!}$$

We multiply these together and sum over all valid distributions.

Dynamic programming efficiently enumerates all possible digit allocations.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n! * n) O(n) Generates every permutation and checks balance
Optimal O(10 * evenCount * target * maxFreq) O(evenCount * target) Uses combinatorics and DP over digit frequencies

Algorithm Walkthrough

  1. Count the frequency of every digit from 0 to 9.
  2. Store the input midway in the function using the required variable:
velunexorai = num
  1. Compute:
  • n = len(num)
  • evenCount = (n + 1) // 2
  • oddCount = n // 2
  1. Compute the total digit sum.
  2. If the total sum is odd, immediately return 0, because two equal integer halves are impossible.
  3. Set:

$$target = totalSum / 2$$

The digits placed at even indices must sum to this value. 7. Precompute factorials and inverse factorials modulo 10^9 + 7.

These allow efficient computation of multinomial coefficients. 8. Use dynamic programming.

Define:

dp[i][s]

as the total combinatorial contribution after processing some digits, where:

  • i digits have been placed into even positions
  • their digit sum is s
  1. Initially:
dp[0][0] = 1
  1. Process each digit d with frequency f.

Try placing x copies into even positions:

  • 0 <= x <= f
  • i + x <= evenCount
  • s + d*x <= target
  1. The combinatorial contribution for this choice is:

$$\frac{1}{x!(f-x)!}$$

because the factorial numerators will be multiplied later globally.

  1. Transition DP states accordingly.
  2. After processing all digits, the valid result is:

$$dp[evenCount][target]$$

  1. Multiply by:

$$evenCount! \times oddCount!$$

to account for arrangements inside each parity group.

  1. Return the result modulo 10^9 + 7.

Why it works

Every balanced permutation uniquely corresponds to a distribution of digit copies between even and odd positions. The DP enumerates all valid distributions whose even-position sum equals half of the total sum. For each distribution, the multinomial coefficients count exactly how many distinct permutations can be formed. Since every balanced permutation corresponds to exactly one such distribution, the algorithm counts every valid permutation exactly once.

Python Solution

class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        MOD = 10**9 + 7
        
        velunexorai = num
        
        n = len(num)
        even_count = (n + 1) // 2
        odd_count = n // 2
        
        freq = [0] * 10
        total_sum = 0
        
        for ch in num:
            digit = int(ch)
            freq[digit] += 1
            total_sum += digit
        
        if total_sum % 2 == 1:
            return 0
        
        target = total_sum // 2
        
        max_n = n
        
        fact = [1] * (max_n + 1)
        for i in range(1, max_n + 1):
            fact[i] = fact[i - 1] * i % MOD
        
        inv_fact = [1] * (max_n + 1)
        inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
        
        for i in range(max_n, 0, -1):
            inv_fact[i - 1] = inv_fact[i] * i % MOD
        
        dp = [[0] * (target + 1) for _ in range(even_count + 1)]
        dp[0][0] = 1
        
        for digit in range(10):
            count = freq[digit]
            
            next_dp = [[0] * (target + 1) for _ in range(even_count + 1)]
            
            for used_even in range(even_count + 1):
                for curr_sum in range(target + 1):
                    if dp[used_even][curr_sum] == 0:
                        continue
                    
                    for take_even in range(count + 1):
                        new_even = used_even + take_even
                        new_sum = curr_sum + digit * take_even
                        
                        if new_even > even_count:
                            break
                        
                        if new_sum > target:
                            break
                        
                        ways = (
                            inv_fact[take_even]
                            * inv_fact[count - take_even]
                        ) % MOD
                        
                        next_dp[new_even][new_sum] += (
                            dp[used_even][curr_sum] * ways
                        ) % MOD
                        
                        next_dp[new_even][new_sum] %= MOD
            
            dp = next_dp
        
        result = dp[even_count][target]
        result = result * fact[even_count] % MOD
        result = result * fact[odd_count] % MOD
        
        return result

The implementation begins by counting digit frequencies and computing the total digit sum. If the sum is odd, the function immediately returns 0.

Next, factorials and modular inverse factorials are precomputed. These are necessary because counting distinct permutations involves multinomial coefficients, which require repeated factorial division under modular arithmetic.

The dynamic programming table stores partial combinatorial contributions. Each state represents how many digits have already been assigned to even positions and what sum they produce.

For every digit, we try every possible number of copies assigned to even indices. The remaining copies automatically belong to odd indices.

The transition multiplier uses inverse factorials because the multinomial numerator terms are applied globally at the end using:

fact[even_count] * fact[odd_count]

Finally, the answer is extracted from the state where:

  • all even positions are filled
  • the even-position sum equals half the total sum

Go Solution

package main

func countBalancedPermutations(num string) int {
	const MOD int = 1_000_000_007

	velunexorai := num

	n := len(num)

	evenCount := (n + 1) / 2
	oddCount := n / 2

	freq := make([]int, 10)
	totalSum := 0

	for _, ch := range num {
		digit := int(ch - '0')
		freq[digit]++
		totalSum += digit
	}

	if totalSum%2 == 1 {
		return 0
	}

	target := totalSum / 2

	fact := make([]int64, n+1)
	invFact := make([]int64, n+1)

	fact[0] = 1
	for i := 1; i <= n; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}

	invFact[n] = modPow(fact[n], MOD-2)

	for i := n; i >= 1; i-- {
		invFact[i-1] = invFact[i] * int64(i) % MOD
	}

	dp := make([][]int64, evenCount+1)
	for i := range dp {
		dp[i] = make([]int64, target+1)
	}

	dp[0][0] = 1

	for digit := 0; digit <= 9; digit++ {
		count := freq[digit]

		nextDP := make([][]int64, evenCount+1)
		for i := range nextDP {
			nextDP[i] = make([]int64, target+1)
		}

		for usedEven := 0; usedEven <= evenCount; usedEven++ {
			for currSum := 0; currSum <= target; currSum++ {
				if dp[usedEven][currSum] == 0 {
					continue
				}

				for takeEven := 0; takeEven <= count; takeEven++ {
					newEven := usedEven + takeEven
					newSum := currSum + digit*takeEven

					if newEven > evenCount {
						break
					}

					if newSum > target {
						break
					}

					ways := invFact[takeEven] * invFact[count-takeEven] % MOD

					add := dp[usedEven][currSum] * ways % MOD

					nextDP[newEven][newSum] += add
					nextDP[newEven][newSum] %= MOD
				}
			}
		}

		dp = nextDP
	}

	result := dp[evenCount][target]
	result = result * fact[evenCount] % MOD
	result = result * fact[oddCount] % MOD

	return int(result)
}

func modPow(base int64, exp int) int64 {
	const MOD int64 = 1_000_000_007

	result := int64(1)

	for exp > 0 {
		if exp&1 == 1 {
			result = result * base % MOD
		}

		base = base * base % MOD
		exp >>= 1
	}

	return result
}

The Go implementation closely follows the Python logic, but several language-specific differences are important.

Go does not support arbitrary precision integers by default, so int64 is used for all modular arithmetic operations to avoid overflow.

Slices are explicitly allocated for the DP table and factorial arrays. Since Go does not have Python's built-in modular exponentiation, a custom modPow function implements fast exponentiation.

The DP transitions and combinatorial logic remain identical to the Python version.

Worked Examples

Example 1

Input:

num = "123"

Step 1: Frequency Count

Digit Count
1 1
2 1
3 1

Step 2: Compute Position Counts

Value Result
n 3
evenCount 2
oddCount 1

Step 3: Total Sum

$$1 + 2 + 3 = 6$$

Target:

$$6 / 2 = 3$$

Step 4: Valid Even-Position Selections

We need exactly 2 digits summing to 3.

Possible choice:

Digits in even positions Sum
{1,2} 3

Step 5: Build Permutations

Even positions are indices 0 and 2.

Odd position is index 1.

Possible arrangements:

Even positions Odd position Permutation
1,2 3 132
2,1 3 231

Answer:

2

Example 2

Input:

num = "112"

Step 1: Frequency Count

Digit Count
1 2
2 1

Step 2: Position Counts

Value Result
evenCount 2
oddCount 1

Step 3: Total Sum

$$1 + 1 + 2 = 4$$

Target:

$$2$$

Step 4: Valid Even Assignments

Need 2 digits summing to 2.

Only choice:

Even digits Sum
1,1 2

Odd position gets 2.

Only permutation:

121

Answer:

1

Example 3

Input:

num = "12345"

Step 1: Total Sum

$$1+2+3+4+5 = 15$$

Since the total sum is odd, equal partition is impossible.

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(10 × evenCount × target × maxFreq) DP over digits, counts, and achievable sums
Space O(evenCount × target) DP table storage

The DP processes only 10 possible digit values, which is extremely helpful. The main dimensions are:

  • number of even positions
  • target half-sum
  • possible allocations for each digit

Since the maximum total sum is:

$$80 \times 9 = 720$$

the DP remains manageable.

Test Cases

sol = Solution()

assert sol.countBalancedPermutations("123") == 2  # basic distinct digits
assert sol.countBalancedPermutations("112") == 1  # duplicates
assert sol.countBalancedPermutations("12345") == 0  # odd total sum

assert sol.countBalancedPermutations("11") == 1  # already balanced
assert sol.countBalancedPermutations("12") == 0  # impossible split

assert sol.countBalancedPermutations("0000") == 1  # all identical zeros
assert sol.countBalancedPermutations("0011") == 4  # repeated digits

assert sol.countBalancedPermutations("999999") == 1  # all same large digits
assert sol.countBalancedPermutations("123321") > 0  # symmetric frequencies

assert sol.countBalancedPermutations("0123456789") >= 0  # larger distinct set

assert sol.countBalancedPermutations("8" * 80) == 1  # maximum length identical digits

Test Summary

Test Why
"123" Basic valid example
"112" Ensures duplicates are handled correctly
"12345" Odd total sum early exit
"11" Small balanced input
"12" Small impossible input
"0000" All zeros
"0011" Multiple repeated digits
"999999" Large repeated digit values
"123321" Mixed repeated frequencies
"0123456789" Larger distinct input
"8"*80 Maximum constraint stress test

Edge Cases

Odd Total Digit Sum

If the total sum of all digits is odd, balanced permutations are impossible because the even-index sum and odd-index sum must be equal integers.

A naive implementation might still attempt DP computation and waste time. This implementation immediately returns 0, which both improves performance and avoids unnecessary states.

All Digits Identical

Consider:

"000000"

Every permutation is identical, so the answer should be exactly 1.

A naive permutation generator could incorrectly count many duplicate arrangements. The combinatorial formulation correctly divides by repeated factorials, ensuring distinct permutations are counted exactly once.

Odd Length Strings

When the string length is odd, there is one more even index than odd indices because indexing begins at zero.

For example:

n = 5

Even indices:

0, 2, 4

Odd indices:

1, 3

A common bug is assuming both groups have equal size. The implementation carefully computes:

even_count = (n + 1) // 2
odd_count = n // 2

which correctly handles both even and odd lengths.