題目網址：https://leetcode.cn/problems/longest-repeating-character-replacement/

題意：給一 string s 和一整數 k, 你可以選擇將 s 中的任意字元變成其他大寫英文字母, 該操作最多執行 k 次。

經上述操作後, 返回僅包含相同字元的最大 substring 長度。

s 由大寫英文字母所組成。

Solution 1：

想法：利用 Sliding Window, 將 window 中的元素分成兩部分

  • 出現頻率最多的元素
  • 扣掉出現頻率最多的元素後，所剩餘的元素

若剩餘的元素個數 ≤ k, 代表剩餘的元素可全部替換為頻率最多的元素。反之, 則不行。做完後, 更新 res

class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0, right = 0, res = 0;
        vector<int> window(26, 0);

        while (right < s.size()) {
            const char c = s[right];
            ++window[c - 'A'];
            ++right;

            // 若剩餘元素個數 > k，則縮小窗口
            while (right - left - *max_element(window.begin(), window.end()) > k) {
                const char d = s[left];
                --window[d - 'A'];
                ++left;
            }
            res = max(res, right - left);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ $O(26 \cdot n)$, s 中的每個元素最多被遍歷 2 次（left、right）
    • $O(26 \cdot n)$：while loop 中每次取 max_element() 需 $O(26)$
  • space：$O(1)$ ➔ window

Solution 2:

想法: 改善 Solution 1, 將 max_element() 提出, 變成在 while loop 外部維護, 而非在 while loop 中維護

  • 能這樣做是因為在內層 while loop 中移除 window[s[left]] 後, maxf 只會越來越小
  • 也就是說 right - left - maxf(移除前) ≥ right - left - maxf(移除後) 始終是成立的, 因為 maxf(移除後) ≤ maxf(移除前)
  • 若 right - left - maxf(移除前) > k 成立, 則 right - left - maxf(移除後) > k 也必定成立, 因此根本不必在 while loop 中更新 maxf
class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0, right = 0, res = 0;
        unordered_map<char, int> window;

        while (right < s.size()) {
            const char c = s[right];
            ++window[c];
            ++right;

            // 取出 widnow 中出現頻率最高的 char 的個數
            const int maxf = max_element(window.begin(), window.end(), [](auto& p1, auto& p2){
                return p1.second < p2.second;
            })->second;

            while (right - left - maxf > k) {
                const char d = s[left];
                --window[d];
                ++left;
            }

            res = max(res, right - left);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ s 中的每個元素最多被遍歷 2 次（left、right）
  • space：$O(1)$ ➔ window 長度為 $O(26)$