Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A balanced permutation splits the total digit sum equally between the two index-parity classes. If the total is odd, this is impossible. Otherwise, distribute copies of each digit between the two classes and count which still-empty positions receive them. Identical copies must not be counted as distinct objects.

Approach

Count digit frequencies and set the target sum to half the total. Memoize a state containing the next digit to process, the remaining slots in each parity class, and the remaining target for the class with ceil(n / 2) positions. Process digits from nine down to zero.

If digit d occurs f times, try placing j copies in the first class and f - j in the second. Multiply the recursive count by C(firstSlots, j) * C(secondSlots, f - j), then reduce the slot counts and subtract d * j from the target. Impossible states contribute zero; filling all slots with target zero contributes one.

The binomial factors choose positions, so equal digits are not overcounted. Once one class has half the total, the other necessarily does too. Sum all allocations modulo 1,000,000,007.

class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        MOD = 10**9 + 7
        num = [int(x) for x in num]
        total = sum(num)

        if total % 2 == 1:
            return 0

        map = defaultdict(int)
        for x in num:
            map[x] += 1
        n = len(num)
        target = total // 2

        @cache
        def dp(i, odd, even, target):
            if odd == 0 and even == 0 and target == 0:
                return 1
            if i < 0 or odd < 0 or even < 0 or target < 0:
                return 0
            res = 0
            for j in range(map[i] + 1):
                res += comb(odd, j) * comb(even, map[i] - j) * dp(i - 1, odd - j, even - (map[i] - j), target - i * j)
            return res % MOD

        return dp(9, n - (n // 2), n // 2, target)

Complexity analysis

Let n be the digit-string length and S its digit sum. With ten digit levels, the remaining slot total is fixed at each level, so there are O(n*(S + 1)) memo states, each trying O(n) allocations. Repeated exact binomial evaluation gives a conservative O(n^3*(S + 1)) arithmetic-operation bound; using S + 1 includes all-zero input. This is not a unit-bit cost claim: binomial intermediates and Python's unreduced state accumulator use O(n + log MOD) bits. A conservative schoolbook bit-time bound is O(n^5*(S + 1)) for fixed MOD. Auxiliary space is O(n*(S + 1)) memo entries holding modular counts, plus O(n) digit storage and temporary integer bits. Recursion has only ten digit levels.