3014. Minimum Number of Pushes to Type Word I

題目 / Problem

中文： 給你一個字串 word，裡面全是不重複的小寫英文字母。電話鍵盤上編號 2 到 9 的按鍵，每個可以對應一組字母；按第 1 個字母要按 1 次，第 2 個字母要按 2 次，依此類推。你可以自由地把字母重新分配到這 8 個按鍵上，但每個字母只能屬於一個按鍵。請算出打完整個 word 所需要的最少總按鍵次數。

English: You are given a string word consisting of distinct lowercase letters. Keys 2–9 (8 keys) can each hold a group of letters. The 1st letter on a key costs 1 push, the 2nd costs 2 pushes, and so on. You may freely remap letters to keys (each letter belongs to exactly one key). Return the minimum total number of pushes needed to type word.

Constraints / 限制： - 1 <= word.length <= 26 - word 只含小寫字母，且全部不重複 / lowercase letters, all distinct.

Example / 範例： - Input: word = "abcde" → Output: 5 - 5 個字母各放在一個不同的按鍵上，每個都按 1 次：1+1+1+1+1 = 5。 - Five letters go on five separate keys, one push each: 1+1+1+1+1 = 5.

名詞解釋 / Glossary

鍵盤按鍵 / keypad keys：可用來放字母的按鍵只有編號 2~9 共 8 個。0、1、*、# 不放字母。There are exactly 8 usable keys (2–9).
貪心 / greedy：每一步都做「當下看起來最好」的選擇，最後得到全域最佳解。這題的貪心是「先把便宜的位置（按 1 次）填滿，再填按 2 次的位置」。Always fill the cheapest slots (1-push) first, then 2-push slots, etc.
整數除法 / integer division：在 C/C++ 中 a / b 若兩者都是整數，結果會捨去小數（例如 9 / 8 == 1）。We use this to compute which "layer" a letter falls into.
不重複字母 / distinct letters：word 沒有重複字元，所以字母個數就等於字串長度，我們不需要另外統計頻率。Because letters are distinct, the count equals the string length — no frequency counting needed.
原地計數 / running total：用一個變數一邊掃描一邊累加答案，不需要額外的容器。Accumulate the answer in a single variable while looping.

思路

中文： 先想最暴力的想法：我們是不是要枚舉所有「把字母分配到按鍵」的方式，找出總按鍵次數最小的那一種？字母最多 26 個、按鍵 8 個，組合數量非常龐大，這樣做完全不切實際。

換個角度想成本結構。每個按鍵上，第 1 個字母只要按 1 次，第 2 個要按 2 次，第 3 個要按 3 次……也就是說，全鍵盤總共有 8 個「按 1 次」的黃金位置（8 個按鍵各一個），接著有 8 個「按 2 次」的位置，再來 8 個「按 3 次」的位置。要讓總次數最小，顯然要先把所有按 1 次的位置填滿，再填按 2 次的——這就是提示說的「平均分配」。因為每個字母的成本只由它落在第幾層決定，跟是哪個字母無關，而且字母都不重複，所以我們根本不用管字母是什麼，只要看它是第幾個被安排的。

於是答案變成一個簡單公式：把字母依序編號 0, 1, 2, …, n-1，第 i 個字母的成本是 i / 8 + 1（整數除法）。前 8 個（i = 0..7）成本都是 1，接下來 8 個成本是 2，依此類推。把每個字母的成本加起來就是答案。這其實不需要真的去建鍵盤或排序——因為字母不重複，直接對每個位置套公式累加即可。

English: The brute-force idea would be to enumerate every possible assignment of letters to keys and pick the cheapest. With up to 26 letters spread over 8 keys the number of assignments is astronomical, so that's hopeless.

Instead, look at the cost structure. On any key, the 1st letter costs 1 push, the 2nd costs 2, the 3rd costs 3, and so on. Across the whole keypad there are 8 "cost-1" slots (one per key), then 8 "cost-2" slots, then 8 "cost-3" slots, etc. To minimize the total we must fill all the cost-1 slots before using any cost-2 slot — that's the "distribute evenly" hint. A letter's cost depends only on which layer it lands in, not on which letter it is, and since all letters are distinct we don't even care what the letters are — only how many we've placed so far.

That collapses the whole problem into a formula. Number the letters 0, 1, …, n-1; the i-th letter costs i / 8 + 1 using integer division. The first 8 letters cost 1 each, the next 8 cost 2, and so on. Summing these costs gives the answer directly — no keypad, no sorting, no frequency map required.

逐步走查 / Walkthrough

以 word = "abcde"（長度 n = 5）為例，變數 ans 從 0 開始累加。 Using word = "abcde" (n = 5), ans starts at 0 and accumulates.

步驟 i / step	字母 / letter	成本 `i/8 + 1` / cost	累加後 `ans` / running total
0	a	1	1
1	b	1	2
2	c	1	3
3	d	1	4
4	e	1	5

因為只有 5 個字母，全都落在「按 1 次」的第一層（i < 8），所以每步成本都是 1，最終 ans = 5。 All 5 letters fall in the first "cost-1" layer (i < 8), so every push costs 1 and the final answer is ans = 5. ✅

（若字串長度是 9，第 9 個字母 i = 8 會使 8 / 8 = 1，成本變成 2。） (If the length were 9, the 9th letter at i = 8 gives 8 / 8 = 1, so its cost becomes 2.)

Solution — C

// 演算法 / Algorithm:
// 鍵盤有 8 個按鍵。把第 i 個字母(從 0 算起)的成本設為 i/8 + 1:
// 前 8 個按 1 次、接下來 8 個按 2 次…把所有成本加總即為最少總按鍵次數。
// There are 8 keys; letter i (0-indexed) costs i/8 + 1. Sum all costs.

int minimumPushes(char* word) {
    int n = 0;                       // n 記錄字母個數 / n counts the letters
    while (word[n] != '') {        // C 字串以 '' 結尾，逐字元往後數到結尾
        n++;                         // 每遇到一個字元就加一 / count each character
    }
    // 上面等同於算字串長度 strlen(word)，這裡手動寫出讓初學者看清楚
    // The loop above is just strlen(word), written out to show how it works.

    int ans = 0;                     // ans 累加總按鍵次數 / running total of pushes
    for (int i = 0; i < n; i++) {    // 依序處理第 0 到第 n-1 個字母 / for each letter
        // i / 8 是整數除法(捨去小數)，代表這個字母落在第幾「層」
        // i / 8 is integer division; it tells us which cost layer letter i is in
        // + 1 因為每層最少也要按 1 次 / +1 because the cheapest slot still costs 1
        ans += i / 8 + 1;            // 把這個字母的成本加進答案 / add this letter's cost
    }
    return ans;                      // 回傳最少總按鍵次數 / return the minimum pushes
}

Solution — C++

// 演算法 / Algorithm:
// 8 個按鍵。第 i 個字母(0-indexed)成本 = i/8 + 1(前 8 個按 1 次、下 8 個按 2 次…)。
// 因字母不重複,只需按順序把每個成本加總即得最少總按鍵次數。
// 8 keys; letter i costs i/8 + 1. Distinct letters, so just sum the costs.

class Solution {
public:
    int minimumPushes(string word) {
        int n = word.size();         // string::size() 直接取得長度 / length of the word
        int ans = 0;                 // 累加答案 / running total of pushes
        for (int i = 0; i < n; i++) {// 走訪每個字母的位置 / loop over each position
            // i / 8: 整數除法決定成本層 (0,1,2...) / integer division picks the layer
            // + 1: 每層至少按 1 次 / every layer costs at least one push
            ans += i / 8 + 1;        // 加上第 i 個字母的成本 / add cost of letter i
        }
        return ans;                  // 回傳最少總按鍵次數 / return the minimum pushes
    }
};

複雜度 / Complexity

Time: O(n) — 我們只需把每個字母掃一遍並套用固定公式累加，n 是 word 的長度（最多 26）。沒有排序、沒有巢狀迴圈，主導成本就是這一趟線性掃描。We make a single linear pass over the letters, doing constant work each; n is the length of word.
Space: O(1) — 只用了 n、ans、i 幾個整數變數，用量與輸入大小無關。Only a few integer variables are used, independent of input size.

Pitfalls & Edge Cases

只有 8 個按鍵，不是 9 / Only 8 usable keys, not 9：容易誤以為 1~9 全能放字母，但 1 不放，實際可用的是 2~9 共 8 個，所以公式是 / 8。The divisor is 8 because keys 2–9 are usable — 1 holds no letters.
成本要 +1 / Remember the +1：i / 8 對前 8 個字母是 0，若忘了 + 1 會把第一層算成 0 次按鍵，答案全錯。Without +1, the first 8 letters would count as 0 pushes.
整數除法而非浮點 / Integer division, not floating point：務必讓 i 和 8 都是整數，i / 8 才會自動捨去小數。若不小心用浮點會得到分數，需要額外取整。Keep both operands integers so i / 8 truncates cleanly.
字母不重複，不必統計頻率 / Distinct letters, no frequency map：因為題目保證字母不重複（本題 I 版），字母個數等於字串長度，不需要像進階版那樣先數頻率再排序。This is the "distinct letters" version, so plain position counting suffices.
最短輸入 / Shortest input：長度為 1（如 "a"）時迴圈只跑一次，ans = 0/8 + 1 = 1，結果正確。A single-letter word correctly returns 1.