3343. Count Number of Balanced Permutations

HardMathStringDynamic ProgrammingCombinatorics

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, the goal is to count the number of balanced permutations of a given string num consisting of digits. The strategy employs both combinatorial mathematics and dynamic programming through memoization to efficiently explore potential permutations without redundantly recalculating results for repeated subproblems.

Here's a breakdown of the intuition:

Counting Digits and Summing: Start by counting the occurrences of each digit in num and calculating the total sum of these digits. This sum must be even for a balanced permutation to be possible because it needs to be split equally between the sum of odd indices and even indices in the permutation.
Memoized Search: Use a memoized depth-first search (dfs) strategy. This helps in considering each digit one by one to populate both odd and even indices while ensuring that the arrangement remains balanced at each step.
Recursion with Constraints: The recursive function dfs(i, j, a, b) examines:
- i: The current digit being considered.
- j: The remaining sum required to fill the odd positions.
- a: Remaining number of digits needed for odd positions.
- b: Remaining number of digits needed for even positions.
Base Case and Transition: In the base case, we check if the required balance has been achieved, i.e., if the remaining required sum j is 0 and no further numbers need to be placed in either category (a and b are 0). If conditions are met, it signifies a balanced permutation, and we return 1, else 0.
Combinatorial Choices: For each digit count, calculate how many ways it can be distributed between odd and even indices, respecting constraints like available positions, using combination mathematics (e.g., choosing l positions out of a for odd indices and the rest for even).

By balancing mathematical combinations with careful memoization, the approach ensures that only possible, valid permutations contribute to the total count, thus solving the problem efficiently within computational limits.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Solution Approach

To implement the solution for counting the balanced permutations, we use a combination of memoization and combinatorial mathematics techniques. Here's a step-by-step explanation of the solution approach:

Data Structures:
- Use a Counter to tally the occurrences of each digit in the string num. This helps in determining how many of each digit are available for distribution across odd and even indices.
- An array cnt is used to maintain these counts for easy access during permutation creation.
Initial Checks:
- Calculate the total sum s of all digits. If s is not divisible by 2, it is immediately clear that the number cannot ever be balanced, and we return 0 as the result.
Memoized DFS:
- Define a recursive function dfs(i, j, a, b):
  - Here, i tracks the current digit we are considering.
  - j is the remaining sum needed to balance the digits at odd indices.
  - a is the remaining number of digits to place at odd indices, and b is for even indices.
- The solution uses the cache decorator for memoization to avoid recomputing results for the same state (i, j, a, b).
Recursive Logic:
- Base Case: If all digits from 0 to 9 have been considered (i > 9), we return True (1) if the remaining required sum j, and remaining counts a and b, are all zero, indicating a balanced state.
- Prune the search tree by returning 0 if impossible configurations are found, such as when a == 0 but j > 0.
Combining Combinatorial Choices:
- For each permissible partition of digit i into odd and even positions (l and r respectively), calculate the number of ways such a partition can happen using combinatorial math:
  - comb(a, l): Ways to place l of digit i into a positions.
  - comb(b, r): Ways to place the remaining r into b positions.
- Calculate the total contribution of current configuration t to the overall count by multiplying the combinations and recursively calling dfs for the next digit with updated parameters.
Final Answer:
- Start the recursion with dfs(0, s // 2, n // 2, (n + 1) // 2). Here, s // 2 is the target sum for either odd or even indices, and (n + 1) // 2 ensures correct handling of odd-length strings.
- Return the result modulo 10^9 + 7 to meet problem constraints on the result size.

This systematic approach ensures the permutation count is calculated correctly without repeatedly solving the same subproblems, making the solution efficient and scalable for larger inputs.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to clarify the solution approach. Consider the string num = "1123".

Data Structures:
- Use a Counter to count the digits. For "1123", the counts are {'1': 2, '2': 1, '3': 1}.
- Array cnt is represented as [2, 1, 1] for digits 1, 2, and 3.
Initial Checks:
- Calculate the total sum of digits: 1 + 1 + 2 + 3 = 7.
- Since 7 is not divisible by 2, an even split isn't possible, so the function returns 0 immediately.

Suppose we adjust the string to num = "1124" for a feasible demonstration:

Data Structures:
- Digit counts: {'1': 2, '2': 1, '4': 1} and cnt = [2, 1, 0, 1].
Initial Checks:
- The sum is 8, which is even, allowing for a balanced permutation.
Memoized DFS:
- Initiate dfs(0, 8 // 2, 4 // 2, (4 + 1) // 2), i.e., dfs(0, 4, 2, 2).
Recursive Logic:
- Begin considering digit 1. Available count is 2.
- Try distributing 2 over indices, ensuring sums remain balanced and track permutations count using combinatorial logic.
Combining Combinatorial Choices:
- Calculate valid distributions for odd/even positions:
  - Choose l = 1 for odd indices and r = 1 for even indices.
  - Calculate comb(2, 1) * comb(2, 1) ways.
Final Answer:
- Repeat recursion for subsequent digits 2 and 4, maintaining balance.
- Continue until base case is satisfied, where contributions accumulate to a modulo 10^9 + 7.
- Return the calculated number of balanced permutations.

This method effectively addresses potential configurations for each digit, ensuring they contribute to the balanced states without unnecessary recomputation.

Solution Implementation

1from collections import Counter
2from functools import cache
3from math import comb
4
5class Solution:
6    def countBalancedPermutations(self, num: str) -> int:
7        # Recursive function using memoization to calculate permutations
8        @cache
9        def dfs(i: int, j: int, a: int, b: int) -> int:
10            # Base case: if index is greater than 9, check if all sets are zero,
11            # indicating that we've found a balanced partition.
12            if i > 9:
13                return (j | a | b) == 0
14          
15            # If no elements are left for set A, but elements are unassigned, return 0.
16            if a == 0 and j:
17                return 0
18
19            ans = 0
20            # Try distributing elements from the current number 'i' to both sets
21            for l in range(min(count[i], a) + 1):
22                r = count[i] - l
23                # Ensure the current element split is valid and fits in the constraints
24                if 0 <= r <= b and l * i <= j:
25                    # Calculate combinations and recursively solve for the next number
26                    temp = comb(a, l) * comb(b, r) * dfs(i + 1, j - l * i, a - l, b - r)
27                    ans = (ans + temp) % MOD
28            return ans
29
30        nums = list(map(int, num))
31        total_sum = sum(nums)
32
33        # If the total sum is odd, it's impossible to split into balanced sums
34        if total_sum % 2:
35            return 0
36
37        n = len(nums)
38        MOD = 10**9 + 7
39        count = Counter(nums)  # Count occurrences of each digit
40        # Call the DFS to solve the problem starting with the first digit
41        return dfs(0, total_sum // 2, n // 2, (n + 1) // 2)
42

1class Solution {
2    // Array to count occurrences of digits 0-9
3    private final int[] digitCount = new int[10];
4    // A large prime number for modulo operations
5    private final int MODULO = (int) 1e9 + 7;
6    // Memoization table for dynamic programming
7    private Integer[][][][] memoizationTable;
8    // Combination matrix to calculate binomial coefficients
9    private long[][] binomialCoefficients;
10
11    // Main function to count balanced permutations
12    public int countBalancedPermutations(String num) {
13        int sumOfDigits = 0;
14        // Count occurrences of each digit in the input number
15        for (char ch : num.toCharArray()) {
16            digitCount[ch - '0']++;
17            sumOfDigits += ch - '0';
18        }
19      
20        // If sum of digits is odd, return 0 as balanced division is not possible
21        if (sumOfDigits % 2 == 1) {
22            return 0;
23        }
24      
25        int numLength = num.length();
26        int halfLength = numLength / 2 + 1;
27
28        // Initialize memoization and combination tables
29        memoizationTable = new Integer[10][sumOfDigits / 2 + 1][halfLength][halfLength + 1];
30        binomialCoefficients = new long[halfLength + 1][halfLength + 1];
31      
32        // Calculate binomial coefficients
33        binomialCoefficients[0][0] = 1;
34        for (int i = 1; i <= halfLength; i++) {
35            binomialCoefficients[i][0] = 1;
36            for (int j = 1; j <= i; j++) {
37                binomialCoefficients[i][j] = (binomialCoefficients[i - 1][j] + binomialCoefficients[i - 1][j - 1]) % MODULO;
38            }
39        }
40
41        // Use DFS and dynamic programming to find the answer
42        return dfs(0, sumOfDigits / 2, numLength / 2, (numLength + 1) / 2);
43    }
44
45    // Recursive function to perform DFS and dynamic programming
46    private int dfs(int digitIndex, int remainingSum, int firstHalfCount, int secondHalfCount) {
47        // If we have processed all digits
48        if (digitIndex > 9) {
49            // Check if the remaining sum and counts are zero, meaning it's balanced
50            return ((remainingSum | firstHalfCount | secondHalfCount) == 0) ? 1 : 0;
51        }
52      
53        // If no more digits can be used in the first half but there's a remaining sum, return 0
54        if (firstHalfCount == 0 && remainingSum != 0) {
55            return 0;
56        }
57      
58        // Check memoization table
59        if (memoizationTable[digitIndex][remainingSum][firstHalfCount][secondHalfCount] != null) {
60            return memoizationTable[digitIndex][remainingSum][firstHalfCount][secondHalfCount];
61        }
62
63        int result = 0;
64      
65        // Try allocating current digitIndex digits between first and second halves
66        for (int leftCount = 0; leftCount <= Math.min(digitCount[digitIndex], firstHalfCount); ++leftCount) {
67            int rightCount = digitCount[digitIndex] - leftCount;
68            if (rightCount >= 0 && rightCount <= secondHalfCount && leftCount * digitIndex <= remainingSum) {
69                // Calculate number of ways and do DFS recursively
70                int tempResult = (int) (binomialCoefficients[firstHalfCount][leftCount] * 
71                                        binomialCoefficients[secondHalfCount][rightCount] % MODULO *
72                                        dfs(digitIndex + 1, remainingSum - leftCount * digitIndex, firstHalfCount - leftCount, secondHalfCount - rightCount) % MODULO);
73                // Sum up results modulo MODULO
74                result = (result + tempResult) % MODULO;
75            }
76        }
77      
78        // Store result in memoization table
79        return memoizationTable[digitIndex][remainingSum][firstHalfCount][secondHalfCount] = result;
80    }
81}
82

1#include <iostream>
2#include <cstring>
3#include <algorithm>
4#include <string>
5using ll = long long;  // Define a type alias for long long
6const int MAX = 80;
7const int MODULO = 1e9 + 7;
8ll combinations[MAX][MAX];
9
10// Lambda function to initialize the combination array
11auto init = [] {
12    combinations[0][0] = 1;  // Base case for combinations
13    for (int i = 1; i < MAX; ++i) {
14        combinations[i][0] = 1;  // There is exactly one way to choose 0 items
15        for (int j = 1; j <= i; ++j) {
16            // Compute combinations using the Pascal's triangle relation
17            combinations[i][j] = (combinations[i - 1][j] + combinations[i - 1][j - 1]) % MODULO;
18        }
19    }
20    return 0;
21}();
22
23class Solution {
24public:
25    // Method to count balanced permutations of a number
26    int countBalancedPermutations(std::string number) {
27        int digitCount[10]{};  // Array to hold counts of each digit (0-9)
28        int sumDigits = 0;     // Sum of all digits in the number
29
30        // Calculate the count of each digit and the total sum of digits
31        for (char& c : number) {
32            ++digitCount[c - '0'];
33            sumDigits += c - '0';
34        }
35
36        // If the sum of digits is odd, balanced permutations are impossible
37        if (sumDigits % 2 != 0) {
38            return 0;
39        }
40
41        int length = number.size();               // Length of the number
42        int halfLengthPlusOne = length / 2 + 1;   // Calculate n/2 + 1
43
44        // Memoization array for depth-first search (DFS)
45        int memo[10][sumDigits / 2 + 1][halfLengthPlusOne][halfLengthPlusOne + 1];
46        std::memset(memo, -1, sizeof(memo));  // Initialize memoization array with -1
47      
48        // Define a recursive lambda function for DFS
49        auto dfs = [&](auto&& dfs, int i, int j, int a, int b) -> int {
50            if (i > 9) {
51                return ((j | a | b) == 0 ? 1 : 0);  // If j, a, b are all zero, return 1
52            }
53            if (a == 0 && j) {
54                return 0;  // If no more slots but j > 0, return 0
55            }
56            if (memo[i][j][a][b] != -1) {
57                return memo[i][j][a][b];  // Return memoized result if available
58            }
59          
60            int ans = 0;
61            // Iterate over possible numbers of i-th digit in the first half
62            for (int l = 0; l <= std::min(digitCount[i], a); ++l) {
63                int r = digitCount[i] - l;  // Remaining digits in the second half
64                if (r >= 0 && r <= b && l * i <= j) {
65                    // Calculate number of ways and add to answer
66                    int temp = combinations[a][l] * combinations[b][r] % MODULO * dfs(dfs, i + 1, j - l * i, a - l, b - r) % MODULO;
67                    ans = (ans + temp) % MODULO;
68                }
69            }
70            return memo[i][j][a][b] = ans;  // Store result in memoization array
71        };
72      
73        // Start DFS with initial conditions
74        return dfs(dfs, 0, sumDigits / 2, length / 2, (length + 1) / 2);
75    }
76};
77
78// Example usage
79int main() {
80    Solution solution;
81    std::string num = "1122";
82    std::cout << solution.countBalancedPermutations(num) << std::endl;
83    return 0;
84}
85

1const MX = 80; // Maximum value for generating combinations
2const MOD = 10 ** 9 + 7; // Modulo value for operations
3
4// Create and initialize a 2D array for combinations
5const c: number[][] = Array.from({ length: MX }, () => Array(MX).fill(0));
6
7// Initialization function to fill the combination array using Pascal's triangle
8(function init() {
9    c[0][0] = 1;
10    for (let i = 1; i < MX; i++) {
11        c[i][0] = 1;
12        for (let j = 1; j <= i; j++) {
13            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
14        }
15    }
16})();
17
18// Function to count balanced permutations of the input number string
19function countBalancedPermutations(num: string): number {
20    const digitCount = Array(10).fill(0); // Array to store the count of each digit (0-9)
21    let digitSum = 0; // Sum of digits in the input string
22
23    // Calculate the frequency of each digit and the total sum of digits
24    for (const ch of num) {
25        digitCount[+ch]++;
26        digitSum += +ch;
27    }
28
29    // If the sum of digits is odd, balanced permutation is not possible
30    if (digitSum % 2 !== 0) {
31        return 0;
32    }
33
34    const n = num.length; // Length of the number string
35    const halfLength = Math.floor(n / 2) + 1;
36
37    // Memoization object to store intermediate results
38    const memo: Record<string, number> = {};
39
40    // Recursive function for depth-first search with memoization
41    const dfs = (digit: number, sum: number, leftLength: number, rightLength: number): number => {
42        if (digit > 9) {
43            // When all digits are processed, check if the conditions are satisfied
44            return (sum | leftLength | rightLength) === 0 ? 1 : 0;
45        }
46        if (leftLength === 0 && sum > 0) {
47            return 0; // No valid permutation if left half has no remaining slots
48        }
49
50        const key = `${digit},${sum},${leftLength},${rightLength}`;
51        if (key in memo) {
52            return memo[key]; // Return cached result if available
53        }
54
55        let result = 0;
56        // Try distributing digit 'digit' across both halves
57        for (let leftCount = 0; leftCount <= Math.min(digitCount[digit], leftLength); leftCount++) {
58            const rightCount = digitCount[digit] - leftCount;
59            if (rightCount >= 0 && rightCount <= rightLength && leftCount * digit <= sum) {
60                // Calculate the result using the combination formula
61                const contribution = Number(
62                    (((BigInt(c[leftLength][leftCount]) * BigInt(c[rightLength][rightCount])) % BigInt(MOD)) *
63                        BigInt(dfs(digit + 1, sum - leftCount * digit, leftLength - leftCount, rightLength - rightCount))) %
64                    BigInt(MOD)
65                );
66                result = (result + contribution) % MOD; // Accumulate results
67            }
68        }
69        memo[key] = result; // Store result in the memoization table
70        return result;
71    };
72
73    return dfs(0, digitSum / 2, Math.floor(n / 2), Math.floor((n + 1) / 2));
74}
75

Time and Space Complexity

The time complexity of the given solution is O(|\Sigma| \times n^2 \times (n + |\Sigma|)), where |\Sigma| represents the number of different digits (0-9) and thus |\Sigma| = 10. This comes from iterating through each digit with potential combinations of selecting digits from the half a[left] and b[right], involving calculations with the combination function, and each recursion depth spanning through 10 digits, summing to n and resulting in twice of dfs.

The space complexity is O(n^2 \times |\Sigma|^2). The space is used by the memoization/cache from the recursive function dfs, wherein each state requires storing combinations regarding remaining digits, sum, and split across a and b contributing space in proportion to n^2 possibilities for digit selections and memoization handling for the number of unique digits |\Sigma|.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know