Problem Informations

Problem Index: 3343
Problem Link: Count Number of Balanced Permutations
Topics: Math, String, Dynamic Programming, Combinatorics

Problem Description

You are given a string num. A string of digits is called balanced if the sum of the digits at even indices is equal to the sum of the digits at odd indices.

Return the number of distinct permutations of num that are balanced.

Since the answer may be very large, return it modulo $10^9 + 7$.

A permutation is a rearrangement of all the characters of a string.

Example 1:

Input: num = "123"

Output: 2

Explanation:

The distinct permutations of num are "123", "132", "213", "231", "312", and "321".
Among them, "132" and "231" are balanced. Thus, the answer is 2.

Example 2:

Input: num = "112"

Output: 1

Explanation:

The distinct permutations of num are "112", "121", and "211".
Only "121" is balanced. Thus, the answer is 1.

Example 3:

Input: num = "12345"

Output: 0

Explanation:

None of the permutations of num are balanced, so the answer is 0.

Constraints:

$2 \leq \text{num.length} \leq 80$
num consists of digits '0' to '9' only.

Intuition

The problem aims to find the number of distinct permutations of a given numeric string that are “balanced.” A string is defined as balanced if the sum of the digits at even indices equals the sum of the digits at odd indices. Given the restrictive constraint that permutations can be large, we must seek an efficient means to solve the problem, leading to the application of dynamic programming and combinatorial mathematics. The approach involves examining ways to distribute the digits such that the cumulative constraints are satisfied, particularly the parity sum condition.

Approach

The primary solution strategy is built upon the use of combinatorial combinations and dynamic programming. We will precompute factorials and their modular inverses to facilitate efficient calculation of combinations. Here’s a detailed explanation of the algorithmic approach:

Precomputation of Factorials and Inverses:
- We precompute factorial values and their modular inverses using Fermat’s Little Theorem, enabling fast computation of combinations modulo $10^9 + 7$.
Initial Setup:
- Determine the total length $n$ of the string num and calculate the count of each digit from 0 to 9.
- Compute the total sum of all digits in the string. If this sum is not even, immediately return 0 as it’s impossible to equally partition the sum between even and odd indices.
Dynamic Programming Table Setup:
- We initialize a DP table with dimensions [$targetSum + 1 \times halfLength + 1$], where targetSum is half of the total sum of digits, and halfLength is $n/2$, representing the number of odd positions in the string. The table will store the number of ways to achieve specific sums using a certain number of odd-indexed digits.
DP Transition:
- For each digit (from 0 to 9), if the digit is present in num, iterate over possible ways to distribute occurrences of the digit between odd and even indexed positions.
- For each combination of sums and odd index counts, compute new sums and validate whether they conform to digit limitations and balance conditions. Use precomputed combinations to calculate the number of ways to achieve these new configurations.
Final Result Extraction:
- After processing all digits, retrieve the value from the DP table that corresponds to achieving the targetSum using exactly $halfLength$ odd-indexed digits. This value represents the number of distinct balanced permutations of num.

This method ensures that we systematically explore viable configurations, leveraging symmetry and combinatorial properties to efficiently navigate the problem space.

Code

C++

class Solution {
public:
    const int MOD = 1e9 + 7;         // Modulo value for large numbers
    const int MAXN = 85;             // Maximum length based on constraints
    long long fac[MAXN], inv[MAXN];  // Arrays to store factorials and their modular inverses

    // Precompute factorials and their inverses
    void initComb() {
        fac[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            fac[i] = fac[i - 1] * i % MOD;
        }
        inv[MAXN - 1] = modpow(fac[MAXN - 1], MOD - 2);
        for (int i = MAXN - 2; i >= 0; i--) {
            inv[i] = inv[i + 1] * (i + 1) % MOD;
        }
    }

    // Calculates a^b mod MOD using binary exponentiation
    long long modpow(long long a, long long b) {
        long long res = 1;
        a %= MOD;
        while (b > 0) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    // Combination C(n, k) with modulo
    long long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
    }

    // Main function to count balanced permutations
    int countBalancedPermutations(string num) {
        int n = num.length();       // Length of the input string
        vector<int> digitCount(10, 0); // Count of each digit from 0 to 9
        for (char c : num) digitCount[c - '0']++;
        
        int halfLength = n / 2;     // Half of the string length
        int totalSum = 0;           // Total sum of all digits
        for (int i = 0; i < 10; i++) {
            totalSum += digitCount[i] * i;
        }
        
        // Return 0 if total sum is not even
        if (totalSum % 2 != 0) return 0;
        int targetSum = totalSum / 2;  // Target sum for even and odd indices
        
        initComb();  // Initialize combinations

        // Initialize the DP table for storing the number of ways
        vector<vector<long long>> prev(targetSum + 1, vector<long long>(halfLength + 1, 0));
        prev[0][0] = 1;
        
        int usedDigits = 0;  // Number of digits used so far
        for (int d = 0; d <= 9; d++) {
            if (digitCount[d] == 0) continue;  // Skip digits not present
            
            vector<vector<long long>> curr(targetSum + 1, vector<long long>(halfLength + 1, 0));

            for (int sum = 0; sum <= targetSum; sum++) {
                for (int odd = 0; odd <= halfLength; odd++) {
                    long long ways = prev[sum][odd];
                    if (ways == 0) continue;

                    // Try placing 'j' digits 'd' on odd indices
                    for (int j = 0; j <= digitCount[d]; j++) {
                        int k = digitCount[d] - j;  // Number of digits on even indices
                        int newOdd = odd + j;
                        int newEven = usedDigits - odd + k;
                        
                        // Ensure new counts don't exceed half lengths
                        if (newOdd > halfLength || newEven > n - halfLength) continue;
                        int newSum = sum + j * d;
                        if (newSum > targetSum) continue;
                        
                        // Calculate and add new combinations
                        long long add = ways * C(odd + j, j) % MOD;
                        add = add * C(usedDigits - odd + k, k) % MOD;
                        curr[newSum][newOdd] = (curr[newSum][newOdd] + add) % MOD;
                    }
                }
            }

            usedDigits += digitCount[d];
            prev.swap(curr);  // Move to current state for next digit
        }

        return prev[targetSum][halfLength];  // Return the final count of balanced permutations
    }
};

Python

class Solution:
    MOD = 10**9 + 7         # Modulo value for large numbers
    MAXN = 85               # Maximum length based on constraints
    fac = [0] * MAXN        # Arrays to store factorials
    inv = [0] * MAXN        # Arrays to store their modular inverses

    # Precompute factorials and their inverses
    def initComb(self):
        self.fac[0] = 1
        for i in range(1, self.MAXN):
            self.fac[i] = self.fac[i - 1] * i % self.MOD
        self.inv[self.MAXN - 1] = self.modpow(self.fac[self.MAXN - 1], self.MOD - 2)
        for i in range(self.MAXN - 2, -1, -1):
            self.inv[i] = self.inv[i + 1] * (i + 1) % self.MOD

    # Calculates a^b mod MOD using binary exponentiation
    def modpow(self, a, b):
        res = 1
        a %= self.MOD
        while b > 0:
            if b & 1:
                res = res * a % self.MOD
            a = a * a % self.MOD
            b >>= 1
        return res

    # Combination C(n, k) with modulo
    def C(self, n, k):
        if k < 0 or k > n:
            return 0
        return self.fac[n] * self.inv[k] % self.MOD * self.inv[n - k] % self.MOD

    # Main function to count balanced permutations
    def countBalancedPermutations(self, num):
        n = len(num)                     # Length of the input string
        digitCount = [0] * 10            # Count of each digit from 0 to 9
        for c in num:
            digitCount[int(c)] += 1
        
        halfLength = n // 2              # Half of the string length
        totalSum = 0                     # Total sum of all digits
        for i in range(10):
            totalSum += digitCount[i] * i
        
        # Return 0 if total sum is not even
        if totalSum % 2 != 0:
            return 0
        targetSum = totalSum // 2        # Target sum for even and odd indices
        
        self.initComb()                  # Initialize combinations

        # Initialize the DP table for storing the number of ways
        prev = [[0] * (halfLength + 1) for _ in range(targetSum + 1)]
        prev[0][0] = 1
        
        usedDigits = 0                   # Number of digits used so far
        for d in range(10):
            if digitCount[d] == 0:
                continue  # Skip digits not present
            
            curr = [[0] * (halfLength + 1) for _ in range(targetSum + 1)]

            for sum_ in range(targetSum + 1):
                for odd in range(halfLength + 1):
                    ways = prev[sum_][odd]
                    if ways == 0:
                        continue

                    # Try placing 'j' digits 'd' on odd indices
                    for j in range(digitCount[d] + 1):
                        k = digitCount[d] - j  # Number of digits on even indices
                        newOdd = odd + j
                        newEven = usedDigits - odd + k
                        
                        # Ensure new counts don't exceed half lengths
                        if newOdd > halfLength or newEven > n - halfLength:
                            continue
                        newSum = sum_ + j * d
                        if newSum > targetSum:
                            continue
                        
                        # Calculate and add new combinations
                        add = ways * self.C(odd + j, j) % self.MOD
                        add = add * self.C(usedDigits - odd + k, k) % self.MOD
                        curr[newSum][newOdd] = (curr[newSum][newOdd] + add) % self.MOD
                    
            usedDigits += digitCount[d]
            prev, curr = curr, prev  # Move to current state for next digit

        return prev[targetSum][halfLength]  # Return the final count of balanced permutations

Complexity

Time complexity: $O(n \cdot m^2 \cdot k)$
The time complexity is primarily determined by the nested loops and the operations within them. Here, $n$ is the number of different digits (which is at most 10), $m$ is the target sum, which can range up to half of the maximum possible sum of the digits, and $k$ is the length of the num string provided.
- The initial loop over the digits (0 to 9) gives an outer complexity of $O(10)$, but this is constant.
- The loop for sum is $O(m)$, iterating through possible sums up to the target.
- The loop for odd is $O(k)$ since we may choose up to half the length of the string.
- The innermost loop for digit placement can also iterate up to $O(k)$ times.
- The operations within the loop (calculating combinations) are $O(1)$ due to precomputation.
Thus, the overall complexity is $O(n \cdot m^2 \cdot k)$ when considering the loops and checking constraints for potential combinations.
Space complexity: $O(m \cdot k)$
The space complexity is determined by the dynamic programming table prev and curr, each of which is a 2D vector with dimensions $m \times k$, where $m$ is the target sum size, and $k$ is half the length of the input string.
The use of these tables requires $O(m \cdot k)$ space, as only two such tables are maintained at once. Other arrays used, such as fac and inv, are of fixed size $O(1)$ based on the constraints.

CS Note
中

Leetcode 3343. Count Number of Balanced Permutations

Problem Informations

Problem Description

Intuition

Approach

Code

C++

Python

Complexity