424. Longest Repeating Character Replacement

Leetcode

https://leetcode.com/problems/longest-repeating-character-replacement/description/

題目

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

解答

方法一

第一直覺會想遍歷矩陣，然後將其中不一樣的元素替換掉，看最長可以有幾個元素連續

例如：s='AABAB', k=1

從第一個 A 開始找，找到第三個元素 B，因為 k 可以替換一次，所以可以繼續往右找，直到第五個元素 B 發現已經不能替換了，所以最長的連續元素就是第一個 A 到第四個 A 共 4 個

但除了要由左往右找，也需要由右往左找，因為有可能是

例如：s='ABBB', k=1

由左往右找的話，最長的會是 'BBB'，所以也需要由右往左找，這樣最長的會是 'BBBB'

按照這個邏輯寫出來的程式如下：

var characterReplacement = function (s, k) {
    let max = 1;

    // 左往右找
    for (let i = 0; i < s.length; i++) {
        const value = s[i];
        let j = i + 1;
        let rest = k;

        while (j < s.length) {
            if (s[j] === value) {
                j++;
            } else if (rest > 0) {
                rest--;
                j++;
            } else {
                max = Math.max(max, j - i);
                break;
            }
        }
        max = Math.max(max, j - i);
    }

    // 右往左找
    for (let i = s.length - 1; i >= 0; i--) {
        const value = s[i];
        let j = i - 1;
        let rest = k;

        while (j >= 0) {
            if (s[j] === value) {
                j--;
            } else if (rest > 0) {
                rest--;
                j--;
            } else {
                max = Math.max(max, i - j);
                break;
            }
        }
        max = Math.max(max, i - j);
    }

    return max;
};

但其實這個思考方向是錯的，因為有可能 s='ABBBA', k=1，這時不論 左往右 或 右往左 找，能找到最長的字串都是 'BBB'，但實際上應該要是 'BBBB'

方法二 - Sliding widow

從上面 s='ABBBA', k=1 的例子來看，我們可以發現關鍵點是往後找尋字串時不能只看後面的字串是否等於第一個元素(A)，而是需要去計算當下子字串最多元素的是哪一個，例如：

子字串：'ABB'

當找到第三個元素 B 的時候子字串是 'ABB' ，這時候需要紀錄子字串最多的元素是 B (兩個)，然後再去看其他的元素能不能替換，這題的狀況 k=1，剛好可以替換掉第一個 A，接著往下一個元素檢查

子字串：'ABBB'

這時 A 一樣可以被替換掉，所以繼續往下一個元素前進

子字串：'ABBBA'

這時候發現有兩個 A 已經不夠替換了，所以不能再移動右指針往前，這時需要的是移動左邊的指針，盡量排除掉 非最多次數的元素(A)

子字串：'BBBA'

這時 A 又可以被替換掉了，此時右側指針已經到底，尋找結束

以上範例可以看到解題有兩個關鍵：

紀錄當下子字串最多元素的次數
如果子字串中，非最多次數的元素足夠替換掉，那就繼續往前移動右指針，否則移動左指針盡量排除掉 非最多次數的元素

var characterReplacement = function (s, k) {
    let max = 1;
    let l = 0;
    const map = {};

    for (let r = 0; r < s.length; r++) {
        const value = s[r];
        if (map[value] === undefined) {
            map[value] = 1;
        } else {
            map[value]++;
        }

        // 紀錄當下子字串最多元素的次數
        const maxCount = Math.max(...Object.values(map));
        
        if (r - l + 1 <= maxCount + k) {
            // 如果 maxCount + k 足夠替換，更新 max
            max = Math.max(max, r - l + 1);
        } else {
            // 如果非最多次數的元素不夠替換掉
            // 記得將 left 的元素從 map 中移除
            map[s[l]]--;
            // 移動左指針
            l++;
        }
    }

    return max;
};