[Leetcode] 3343. Count Number of Balanced Permutations

https://leetcode.com/problems/count-number-of-balanced-permutations/description/?envType=daily-question&envId=2025-05-09

initial

so computing each perm is nuts but hint gave a dp. But i dont see how a dp value can store a computed value to be used in later computations.

sol

so instead of trying to compute each perm, we dont rly have to do that. instead we calculate how we can arrange a given particular digit in odd and even indexes and minus that digit's freq in odd indexes. Cuz we have set a target as half the sum of our entire string digit, we dont necessarily need to minus and add every possible case. If it is indeed a valid perm, if we set target and minus the numbers at odd indexes, eventually the sum will equal to 0 when all odd and even indexes are filled with numbers.

so for recursion, we wanna try different arrangements of our current digit. So for j in range(counter[digit] + 1): loop is the key to exploring different possibilities for the current digit.

most impt part

For each value of j, we do three things:

1) comb(odd, j): We calculate the number of ways to choose j odd positions out of the odd available positions to place the current digit.

2) comb(even, counter[digit] - j): Since we have counter[digit] total occurrences of the current digit, and we've placed j of them in odd positions, the remaining counter[digit] - j occurrences must be placed in the even available even positions. We calculate the number of ways to choose these even positions.

3) dfs(digit - 1, odd - j, even - (counter[digit] - j), balance - digit * j): This is the crucial recursive call. We are saying:

"Okay, we've decided to place j copies of the current digit in odd positions and counter[digit] - j copies in even positions. There were comb(odd, j) comb(even, counter[digit] - j) ways to do this."
"Now, let's move on to the next smaller digit (digit - 1) and see how we can place it in the remaining odd positions (odd - j) and the remaining even positions (even - (counter[digit] - j)) to eventually reach a balanced state."
"Also, since we placed j copies of the digit digit in odd positions, the current balance has changed by digit j. We need to pass this updated balance to the next recursive call."

class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        counter= Counter(int(ch) for ch in num)
        total = sum(int(ch) for ch in num)

        @cache
        def dfs(digit,odd,even,balance):
            if odd==0 and even==0 and balance==0:
                return 1
            if digit<0 or odd<0 or even<0 or balance<0:
                return 0
            res=0
            for j in range(counter[digit]+1):
                res+= comb(odd,j)*comb(even,counter[digit]-j)*dfs(digit-1,odd-j,even-(counter[digit]-j),balance-digit*j)
            return res%1000000007
        return 0 if total%2 else dfs(9,len(num)-len(num)//2,len(num)//2,total//2)

complexity

time is determined by the 4 states that our dfs processes. digit is 10, odd worse case is n, same for even and for balance, worse case is 9n/2 = 4.5n which is still n.

so it is n^3

space is The dominant factor in the space complexity is the memoization table that stores the results for the O(n^3 possible states of the dfs function. Therefore, the overall space complexity of the solution is O(n^3)