LeetCode 解題筆記：3016. Minimum Number of Pushes to Type Word II

作者：王一哲
日期：2026年7月31日


LeetCode 題目連結：3016. Minimum Number of Pushes to Type Word II

解題想法

中等難度題，3014. Minimum Number of Pushes to Type Word I 的加強版，但是這題 $word$ 之中可以有相同的字母，需要修改一下程式碼。如果要求最低的次數，原則上是先處理 $word$ 之中數量多的字母，數量最多的前 8 個字母按 1 下，第二多的 8 個字母按 2 下，其餘依此類推。我在計算相異字母的數量時使用了，Python collections 函式庫的 Counter，這是專門用來計數的容器，速度很快；於 C++ 則是用 unordered_map，速度比較慢，改用表格計數快很多。

Python 程式碼

字典計數。Runtime: 91 ms, beats 89.97%. Memory: 19.91 MB, beats 77.26%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = Counter(word)  # 計數器
        vals = sorted(cnt.values(), reverse=True)  # 各相異字母對應的數量
        n = len(vals)  # 相異字母數量
        idx = 0  # 從 vals 讀取資料的索引值
        ans = 0  # 答案
        cof = 1  # 要按幾下才能輸入一個字母
        while idx < n:
            m = 0  # 按 cof 下才能輸入的字母數量
            while idx < n and m < 8:  # 最多 8 個字母
                ans += cof * vals[idx]  # 答案加上 cof * 數量
                idx += 1  # 索引值加 1
                m += 1  # m 加 1
            cof += 1  # cof 加 1
        return ans

表格計數。Runtime: 175 ms, beats 39.47%. Memory: 19.86 MB, beats 93.65%.

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = [0] * 26  # 計數器
        for c in word:
            cnt[ord(c) - ord('a')] += 1
        vals = sorted([val for val in cnt if val > 0], reverse=True)  # 各相異字母對應的數量
        n = len(vals)  # 相異字母數量
        idx = 0  # 從 vals 讀取資料的索引值
        ans = 0  # 答案
        cof = 1  # 要按幾下才能輸入一個字母
        while idx < n:
            m = 0  # 按 cof 下才能輸入的字母數量
            while idx < n and m < 8:  # 最多 8 個字母
                ans += cof * vals[idx]  # 答案加上 cof * 數量
                idx += 1  # 索引值加 1
                m += 1  # m 加 1
            cof += 1  # cof 加 1
        return ans

C++ 程式碼

字典計數。Runtime: 28 ms, beats 26.53%. Memory: 26.96 MB, beats 46.22%.

class Solution {
public:
    int minimumPushes(string word) {
        unordered_map<char, int> cnt;  // 計數器
        for(char c : word) cnt[c]++;
        vector<int> vals;  // 各相異字母對應的數量
        for(auto it : cnt) vals.push_back(it.second);
        sort(vals.begin(), vals.end(), greater<int>());  // 由大到小排序
        // 相異字母數量，從 vals 讀取資料的索引值，答案，要按幾下才能輸入一個字母
        int n = (int)vals.size(), idx = 0, ans = 0, cof = 1;  
        while(idx < n) {
            int m = 0;  // 按 cof 下才能輸入的字母數量
            while(idx < n && m < 8) {  // 最多 8 個字母
                ans += cof * vals[idx];  // 答案加上 cof * 數量
                idx++;  // 索引值加 1
                m++;  // m 加 1
            }
            cof++;  // cof 加 1
        }
        return ans;
    }
};

表格計數。Runtime: 4 ms, beats 86.59%. Memory: 25.83 MB, beats 56.49%.

class Solution {
public:
    int minimumPushes(string word) {
        vector<int> cnt (26, 0);  // 計數器
        for(char c : word) cnt[c - 'a']++;
        vector<int> vals;  // 各相異字母對應的數量
        for(int val : cnt) {
            if (val > 0) vals.push_back(val);
        }
        sort(vals.begin(), vals.end(), greater<int>());  // 由大到小排序
        // 相異字母數量，從 vals 讀取資料的索引值，答案，要按幾下才能輸入一個字母
        int n = (int)vals.size(), idx = 0, ans = 0, cof = 1;  
        while(idx < n) {
            int m = 0;  // 按 cof 下才能輸入的字母數量
            while(idx < n && m < 8) {  // 最多 8 個字母
                ans += cof * vals[idx];  // 答案加上 cof * 數量
                idx++;  // 索引值加 1
                m++;  // m 加 1
            }
            cof++;  // cof 加 1
        }
        return ans;
    }
};