Leetcode 3343. Count Number of Balanced Permutations

Jimmy   May 9, 2025   1029 words   ~25 mins
#Math #String #Dynamic Programming #Combinatorics

Table of Contents

題目資訊

題目敘述

你有一個字串 num。當偶數索引位置的數字之和等於奇數索引位置的數字之和時，這個字串叫做平衡的。

返回 num 的不同的 排列中是平衡的個數。

由於答案可能非常大，返回結果對模 $10^9 + 7$ 的餘數。

排列是字串中所有字符的重新排列。

範例 1:

輸入: num = "123"

輸出: 2

解釋:

  • num 的不同排列有 "123"，"132"，"213"，"231"，"312"和"321"。
  • 其中，"132" 和 "231" 是平衡的。因此，答案是 2。

範例 2:

輸入: num = "112"

輸出: 1

解釋:

  • num 的不同排列有 "112"，"121"和"211"。
  • 只有"121"是平衡的。因此，答案是 1。

範例 3:

輸入: num = "12345"

輸出: 0

解釋:

  • num 的排列中沒有一個是平衡的，因此答案是 0。

約束條件:

  • $2 \leq \text{num.length} \leq 80$
  • num 僅由數字 '0' 到 '9' 組成。

直覺

這個問題旨在找出一個給定數字字串所有不同排列組合中，屬於「平衡」的排列的數量。字串被定義為平衡的，當且僅當偶數索引的數字之和等於奇數索引的數字之和。由於排列的數量可能極大，我們必須尋找一種有效的方法來解決問題，這導致我們應用動態規劃和組合數學。該方法包含研究如何分配數字以滿足累積約束，特別是平衡條件的分佈方式。

解法

主要的解決策略是運用組合數學中的組合計算以及動態規劃。我們將預先計算階乘及其模數反數，以便更高效地計算組合。以下是算法方法的詳細說明：

  1. 階乘和模數反數的預先計算：

    • 我們使用費馬小定理預先計算階乘值及其模數反數，以便快速計算模數 $10^9 + 7$ 下的組合。

  2. 初始設置：

    • 確定字串 num 的總長度 $n$，並計算出每個從 0 到 9 的數字出現的次數。
    • 計算字串中所有數字的總和。如果這個總和不是偶數，則立即返回 0，表示不可能將總和等分在奇數和偶數索引中。

  3. 動態規劃表設置：

    • 初始化一個 DP 表，其維度為 $[targetSum + 1 \times halfLength + 1]$，其中 targetSum 是所有數字總和的一半，halfLength 是 $n/2$，代表字串中奇數索引的位置數。這個表將存儲使用特定數量的奇數索引數字來達到特定和的方式數。

  4. 動態規劃轉移：

    • 對於每個數字（從 0 到 9），如果該數字在 num 中存在，則遍歷將該數字的出現次數分配在奇數索引和偶數索引之間的可能方式。
    • 對於每種和及奇數索引數量的組合，計算新的和並確認其是否符合數字限制和平衡條件。利用預先計算的組合來計算達到這些新配置的方式數。

  5. 最終結果提取：

    • 處理完所有數字後，從 DP 表中檢索對應使用正好 $halfLength$ 個奇數索引數字來達到 targetSum 的值。該值代表 num 的不同平衡排列的數量。

此方法確保我們系統地探索可行的配置，利用對稱性和組合性質來高效地導航問題空間。

程式碼

C++

class Solution {
public:
    const int MOD = 1e9 + 7;         // 大數的取模值
    const int MAXN = 85;             // 根據限制條件的最大長度
    long long fac[MAXN], inv[MAXN];  // 陣列，用來儲存階乘和它們的模逆

    // 預先計算階乘和它們的模逆
    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;
        }
    }

    // 使用二進位指數法計算 a^b mod MOD
    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;
    }

    // 計算 C(n, k) 取模
    long long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
    }

    // 計算平衡排列數量的主要函數
    int countBalancedPermutations(string num) {
        int n = num.length();       // 輸入字串的長度
        vector<int> digitCount(10, 0); // 計算每個數字 0 到 9 的數量
        for (char c : num) digitCount[c - '0']++;
        
        int halfLength = n / 2;     // 字串長度的一半
        int totalSum = 0;           // 所有數字的總和
        for (int i = 0; i < 10; i++) {
            totalSum += digitCount[i] * i;
        }
        
        // 如果總和不是偶數則返回 0
        if (totalSum % 2 != 0) return 0;
        int targetSum = totalSum / 2;  // 偶數和奇數索引的目標總和
        
        initComb();  // 初始化組合數

        // 初始化DP表，用來儲存方式的數量
        vector<vector<long long>> prev(targetSum + 1, vector<long long>(halfLength + 1, 0));
        prev[0][0] = 1;
        
        int usedDigits = 0;  // 到目前為止使用的數字數量
        for (int d = 0; d <= 9; d++) {
            if (digitCount[d] == 0) continue;  // 跳過未出現的數字
            
            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;

                    // 嘗試將 'j' 個數字 'd' 放在奇數索引上
                    for (int j = 0; j <= digitCount[d]; j++) {
                        int k = digitCount[d] - j;  // 放在偶數索引上的數字數量
                        int newOdd = odd + j;
                        int newEven = usedDigits - odd + k;
                        
                        // 確保新的計數不會超過一半長度
                        if (newOdd > halfLength || newEven > n - halfLength) continue;
                        int newSum = sum + j * d;
                        if (newSum > targetSum) continue;
                        
                        // 計算並加入新的組合
                        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);  // 移動到下一數字的當前狀態
        }

        return prev[targetSum][halfLength];  // 返回平衡排列的最終數量
    }
};

Python

class Solution:
    MOD = 10**9 + 7         # 大數取模值
    MAXN = 85               # 基於限制的最大長度
    fac = [0] * MAXN        # 用於儲存階乘的陣列
    inv = [0] * MAXN        # 用於儲存模逆的陣列

    # 預先計算階乘及其模逆
    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

    # 使用二元冪運算計算 a^b mod MOD
    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

    # 組合 C(n, k) 並取模
    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

    # 計算平衡排列數量的主函數
    def countBalancedPermutations(self, num):
        n = len(num)                     # 輸入字串的長度
        digitCount = [0] * 10            # 計算每個數字的數量，範圍從0到9
        for c in num:
            digitCount[int(c)] += 1
        
        halfLength = n // 2              # 字串長度的一半
        totalSum = 0                     # 所有數字的總和
        for i in range(10):
            totalSum += digitCount[i] * i
        
        # 如果總和不是偶數則返回0
        if totalSum % 2 != 0:
            return 0
        targetSum = totalSum // 2        # 偶數和奇數索引的目標和
        
        self.initComb()                  # 初始化組合

        # 初始化DP表以儲存方法的數量
        prev = [[0] * (halfLength + 1) for _ in range(targetSum + 1)]
        prev[0][0] = 1
        
        usedDigits = 0                   # 到目前為止使用的數字數量
        for d in range(10):
            if digitCount[d] == 0:
                continue  # 跳過不存在的數字
            
            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

                    # 嘗試將 'j' 個數字 'd' 放在奇數索引位置
                    for j in range(digitCount[d] + 1):
                        k = digitCount[d] - j  # 偶數索引位置的數字數量
                        newOdd = odd + j
                        newEven = usedDigits - odd + k
                        
                        # 確保新的數量不超過半長度
                        if newOdd > halfLength or newEven > n - halfLength:
                            continue
                        newSum = sum_ + j * d
                        if newSum > targetSum:
                            continue
                        
                        # 計算並新增新的組合
                        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  # 轉移到當前狀態以進行下一個數字的計算

        return prev[targetSum][halfLength]  # 返回平衡排列的最終計數

複雜度分析

  • 時間複雜度: $O(n \cdot m^2 \cdot k)$

    時間複雜度主要由巢狀迴圈和其中的操作所決定。這裡，$n$ 是不同數字的數量（最多為10），$m$ 是目標和，可以達到數字可能和的一半，$k$ 是提供的數字字符串的長度。

    • 對數字（0到9）的初始迴圈給出了 $O(10)$ 的外部複雜度，但這是常數。
    • sum 的迴圈為 $O(m)$，遍歷可能的和達到目標。
    • odd 的迴圈為 $O(k)$，因為我們可能選擇字符串長度的一半。
    • 最內部的數字放置迴圈最多也可以迭代 $O(k)$ 次。
    • 迴圈中的操作（計算組合）由於預計算而為 $O(1)$。

    因此，在考慮迴圈和檢查潛在組合的限制時，總體複雜度為 $O(n \cdot m^2 \cdot k)$。

  • 空間複雜度: $O(m \cdot k)$

    空間複雜度由動態規劃表 prev 和 curr 所決定，這兩者都是維度為 $m \times k$ 的二維向量，其中 $m$ 是目標和的大小，$k$ 是輸入字符串長度的一半。

    使用這些表需要 $O(m \cdot k)$ 的空間，因為同時只維持兩個這樣的表。其他使用的數組，如 fac 和 inv，基於限制為固定大小 $O(1)$。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.