題目敘述: Minimum Number of Pushes to Type Word II
給定一個傳統手機鍵盤，如圖所示
現在讓你重新安排每個字母的所在位置，每個字母可以重新安排到2~9這幾個鍵盤上的位置，每個字母限定只能選擇一個數字鍵去對應。
請問重新安排之後，最少要按幾次鍵盤才能輸出給定的字串word?
測試範例
Example 1:
重新安排後的鍵盤最佳配置
Input: word = "abcde"
Output: 5
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
Total cost is 1 + 1 + 1 + 1 + 1 = 5.
It can be shown that no other mapping can provide a lower cost.
Example 2:
重新安排後的鍵盤最佳配置
Input: word = "xyzxyzxyzxyz"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> one push on key 3
"z" -> one push on key 4
Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12
It can be shown that no other mapping can provide a lower cost.
Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.
Example 3:
重新安排後的鍵盤最佳配置
Input: word = "aabbccddeeffgghhiiiiii"
Output: 24
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
"f" -> one push on key 7
"g" -> one push on key 8
"h" -> two pushes on key 9
"i" -> one push on key 9
Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24.
It can be shown that no other mapping can provide a lower cost.
約束條件
Constraints:
1 <= word.length <= 10^5
輸入字串長度介於1~十萬。
wordconsists of lowercase English letters.
輸入字串只會有小寫英文字母。
觀察 如何讓按鍵次數變少?
直覺的想法就是，
讓最頻繁使用到的字元放到第一排，接著放頻率次高的，依此類推，
最後才放頻率最低的到最後一排。
演算法 Greedy策略，根據出現次數進行最佳化
承接觀察點的思考，先建立一個字典，統計每個英文字母的出現次數。
接著進行排序，讓前8個出現次數最高的優先排在第一排，接著放8個次高到第二排，...，依此類推。
核心觀念:用最小的成本(按鍵次數)去服務最常用到的英文字母！
程式碼 Greedy策略，根據出現次數進行最佳化
class Solution:
def minimumPushes(self, word: str) -> int:
# a list of occurrences of characters
occurrence = list( Counter(word).values() )
# Keep in descending order from high frequency to low frequency
occurrence.sort(reverse = True)
# First 8 high frequency characters put on first level
# Second 8 high frequency characters put on second level
# ... and so on
return sum( occ * (i // 8 + 1) for i, occ in enumerate(occurrence) )
複雜度分析
時間複雜度: O(n)
掃描輸入字串的每個字元，耗時O(n)
這個案例中，排序的成本反而比較小 = O(26 log 26) = O(1) = 常數級別
空間複雜度: O(1)
建立字典所需空間最大為O(26) = O(1) = 小寫英文字母的數量
