Count how many distinct permutations of a digit string are balanced between odd and even positions.
You are given a string num consisting only of digits.
Count the number of distinct permutations of its characters such that the sum of the digits placed at odd indices equals the sum of the digits placed at even indices.
Treat indices as 0-based unless the problem statement you are solving specifies otherwise. Two permutations are considered distinct if their resulting strings are different.
Return the count of valid permutations. Since the answer can be very large, the result is typically required modulo a fixed number.
This is a counting problem: the key challenge is handling repeated digits correctly while deciding how many copies of each digit go to each side of the permutation.
Input Format
- A string
numof digits. - The string may contain repeated digits.
You need to count permutations that satisfy the balance condition between the two index groups.
Output Format
- Return an integer representing the number of balanced permutations.
- If a modulus is required by the original platform version, apply it to the final count.
Constraints
1 <= len(num)numcontains only characters0through9.- Repeated digits may appear many times.
- The answer may be large, so counting is usually done with dynamic programming and combinatorics.
Example 1
Input
num = "123"
Output
2
Explanation
The distinct permutations are 123, 132, 213, 231, 312, and 321. Among them, the balanced ones are the permutations where the parity-group sums match. Here, 132 and 231 satisfy the condition.
Example 2
Input
num = "1122"
Output
4
Explanation
There are repeated digits, so identical rearrangements should not be double-counted. The valid balanced permutations are the distinct arrangements that place one 1 and one 2 into each parity group, producing equal sums.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.