Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3637. Count Number of Balanced Permutations

My accepted Python solution to LeetCode problem 3637, Count Number of Balanced Permutations, running in 2186ms.

  • Difficulty: Hard
  • Python
  • Runtime 2186ms
  • Memory 18.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 2186ms, memory 18.2MB, accepted 2025-12-31.

python
class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        MOD = 10**9 + 7
        n = len(num)
        digits = [int(c) for c in num]
        total = sum(digits)
        
        if total % 2 == 1:
            return 0
        
        target = total // 2
        even_count = (n + 1) // 2
        odd_count = n // 2
        
        # Count frequency of each digit
        cnt = [0] * 10
        for d in digits:
            cnt[d] += 1
        
        # Precompute factorials
        max_n = n + 1
        fact = [1] * max_n
        for i in range(1, max_n):
            fact[i] = fact[i-1] * i % MOD
        
        inv_fact = [1] * max_n
        inv_fact[max_n-1] = pow(fact[max_n-1], MOD-2, MOD)
        for i in range(max_n-2, -1, -1):
            inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
        
        def comb(a, b):
            if b < 0 or b > a:
                return 0
            return fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD
        
        # dp[i][j] = number of ways to place i digits with sum j in even positions
        # Each way is counted based on choosing which copies of each digit go to even positions
        dp = [[0] * (target + 1) for _ in range(even_count + 1)]
        dp[0][0] = 1
        
        for d in range(10):
            if cnt[d] == 0:
                continue
            new_dp = [[0] * (target + 1) for _ in range(even_count + 1)]
            for i in range(even_count + 1):
                for j in range(target + 1):
                    if dp[i][j] == 0:
                        continue
                    # Choose k copies of digit d for even positions
                    for k in range(cnt[d] + 1):
                        ni = i + k
                        nj = j + k * d
                        if ni <= even_count and nj <= target:
                            # C(cnt[d], k) ways to choose which k copies go to even positions
                            new_dp[ni][nj] = (new_dp[ni][nj] + dp[i][j] * comb(cnt[d], k)) % MOD
            dp = new_dp
        
        # Now we have the number of ways to assign digits to even vs odd positions
        # Multiply by the number of arrangements within each position group
        ans = dp[even_count][target]
        ans = ans * fact[even_count] % MOD
        ans = ans * fact[odd_count] % MOD
        
        # Divide by the factorial of each digit count (since same digits are indistinguishable)
        for d in range(10):
            ans = ans * inv_fact[cnt[d]] % MOD
        
        return ans

Source