• Leetcode 3389. Minimum Operations to Make Character Frequencies Equal
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3389. Minimum Operations to Make Character Frequencies Equal

1. 解題思路

這一題從答題從test的結果來說來說做出的人很少，主要確實有些繁瑣，因為還是那種分類討論的問題，然后思路上也比較暴力。

這道題我自己也沒有完全自力搞定，因為一開始覺得不會這么暴力，然后就沒怎么找到思路，結果看了一下大佬們的回答之后發現核心思路其實差不多，只不過我覺得鐵定超時就沒有往下去嘗試，然后大佬做了，然后就過了……

這道題思路上如前所述，非常的暴力，就是遍歷所有可能的最終值情況下各自需要多少操作，然后取最小值。

因此，這里的核心問題就變成了，給定一個最終值$k$，如何計算將原始字符串變換為最終所有的字符都為$k$個所需的最小操作次數。

而這個又是可以通過動態規劃來進行實現，只不過每一個值都需要考慮以下幾種情況：

1. 當前值變為$0$，下一個值變為$k$
2. 當前值變為$0$，下一個值也變為$0$
3. 當前值變為$k$，下一個值變為$0$
4. 當前值變為$k$，下一個值也變為$k$

另外，如果當前值如果需要減少現有值的情況下，需要考察下一個值是否需要增加值，如果需要的話需要使用操作3來進行操作復用。

可以看到，這個邏輯還是蠻復雜的，需要一些分類討論，但整體理清楚了思路就整體還是挺直接的了。

2. 代碼實現

我們給出最終的python代碼實現如下：

class Solution:def makeStringGood(self, s: str) -> int:cnt = Counter(s)@lru_cache(None)def count_op(tgt):nums = [cnt[ch] for ch in string.ascii_lowercase]@lru_cache(None)def dfs(idx, nxt):if idx == 25:current = nums[idx] + nxtreturn min(current, abs(tgt-current))ans = math.infcurrent = nums[idx] + nxtnxt = nums[idx+1]if current == 0 or current == tgt:return dfs(idx+1, 0)if nxt == 0 or nxt >= tgt:ans = min(ans, min(current, abs(current-tgt)) + dfs(idx+1, 0))elif current > tgt:ans = min(ans, current-tgt + dfs(idx+1, 0),current-tgt + dfs(idx+1, min(tgt-nxt, current-tgt)))else:ans = min(ans, tgt-current + dfs(idx+1, 0),current + dfs(idx+1, 0),current + dfs(idx+1, min(tgt-nxt, current)))return ansans = dfs(0, 0)return ans              ans = min(count_op(i) for i in range(1, max(cnt.values())+1))return ans

提交代碼評測得到：耗時1115ms，占用內存19.8MB。