424 - Longest Repeating Character Replacement

解法一 - Sliding Window

這題該如何判斷什麼時候要移動 windowStart 呢?

方法就是,我們可以用 Hash Table 記錄目前各 char repeat 的次數,並記錄當前 window 中 repeat 最多的次數(maxRepeatingLen),當 window size - maxRepeatingLen > k 時,我們就知道有超過 k 個 char 得修改,所以必須移動 windowStart 來滿足限制。

有一個比較不直覺的地方是,當我們發現超過 k 個 char 需要修改,所以移動 windowStart 時,我們卻只更新了 Hash Table 而沒有更新 maxRepeatingLen。

這樣做不會錯的原因如下:

It is tricky to use the sliding window. 
The tricky point is if(max + k <= end - start) where max doesn't change, if you decrease count by count[s.charAt(start++)]--.
If the start pointer originally points to maxCount character, max should be decreased as well, but it didn't. 
I hope my example can make it clear. 

Let's say we have AABCDAAA, k = 2. 
When start points to A, the if(max + k <= end - start) will be met after end moves to D. 
So, Count[A] decreases by 1 and start++. 
(Max + k) are still same. 

next, by intuition, max should be 1. Here it actually doesn't matter! 
As we move on, A stills doesn't qualify, but count[A]++. 
Shift window right and we deceases Count[A] = 1. 
MaxCount = 2 still seems to make no sense now. 
So, we shift window towards right. 

Next, A makes Count[A] increased to 2, and maxCount doesn't change. 
Then, shift to right, start = C. 
Now substring is CDAA. Last, count[A]++ and becomes 3. 
That's when maxCount is reached and changed. 
At this point, we found a larger window! 
So it doesn't matter if maxCount is incorrect in the process. Because, we only care about if we get the largest window. 

maxCount is actually larger than actual count because it represents current global maxWindow. 
It means there was a max substring before.

詳細的一些討論可以在這邊看:https://leetcode.com/problems/longest-repeating-character-replacement/discuss/91271/Java-12-lines-O(n)-sliding-window-solution-with-explanation/95833

class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxLen = 0;
        unordered_map<char, int> table;

        int windowStart = 0, maxRepeatingLen = 0;
        for(int windowEnd=0; windowEnd<s.length(); windowEnd++) {
            table[s[windowEnd]]++;
            maxRepeatingLen = max(maxRepeatingLen, table[s[windowEnd]]);

            while(windowEnd-windowStart+1-maxRepeatingLen > k) {
                table[s[windowStart]]--;
                windowStart++;
            }

            maxLen = max(maxLen, windowEnd-windowStart+1);
        }

        return maxLen;
    }
};

延伸題 - Longest Subarray with Ones after Replacement

這題的概念基本上跟上面一樣,不過只會有 0 跟 1 兩種情況,所以不需要用到 unordered_map,實作如下:

using namespace std;

#include <iostream>
#include <vector>

class ReplacingOnes {
public:
  static int findLength(const vector<int>& arr, int k) {
      int maxLen = 0;
      int windowStart = 0, maxOneCount = 0;

      for(int windowEnd=0; windowEnd<arr.size(); windowEnd++) {
          if(arr[windowEnd] == 1) maxOneCount++;

          while(windowEnd-windowStart+1-maxOneCount > k) {
              if(arr[windowStart] == 1) {
                  maxOneCount--;
              }
              windowStart++;
          }

          maxLen = max(maxLen, windowEnd-windowStart+1);
      }

      return maxLen;
  }
};

results matching ""

    No results matching ""