Sliding Window – 陪你刷題

Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。

何謂 sliding window

給定的 input 是線性資料結構,代表你可以循序存取 (sequential access),例如 array, linked list 或 string ,題目要求找出滿足特定條件的最長/最短 substring, subarray 或一個目標值,就可以使用 sliding window 技巧,此技巧有以下特質:

  1. 在線性時間內完成
  2. 透過操控 two pointer 找出滿足條件的區間
  3. 不管是搜索的範圍,或是最終答案,一定都是 continuous 的資料,continuous 代表資料可以 sequential access

直接先來看 leetcode 對應題目,再來探究 Sliding Window 的操作框架會比較有感覺。

  • Leetcode #567 Permutation in String

    題目描述:給你兩個 string s2 和 s1,決定 s2 內是否包含子字串 s1 。

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

如果使用暴力法,在 s2 的不同字元開始去找尋是否包含 s1 的子字串,這樣的時間複雜度就會是 O (n * m) ,其中 n 是小字串的長度, m 是大字串的長度。

如果能夠使用 sliding window 技巧,可以將時間複雜度縮小到僅 O(m) 。

Sliding window 操作框架

/**
 * parent 為搜尋範圍, child 為目標字串
 */
void slidingWindow (string parent, string child)
{
    /* need 用來紀錄目標字串包含的字元與對應的個數 */
    unordered_map<char, int> need, window;
    for (char c:child) need[c]++;

    int left = 0, right = 0;  /* two pointers */
    /**
     * 用來紀錄目標字串各字元對應的個數
     * 是否已經滿足,如果 valid == need.size(),
     * 代表 window 內已經收集完資料
     */
    int valid = 0;
    while (right < parent.size()) {
        // input 是要放入 window 的字元
        char input = s[right];
        // 移動右邊窗口將 window 增大
        right++;
        // 進行 window 內資料更新
        ...

        while (window needs shrink) {
            // out 是要移出 window 的字元
            char out = s[left];
            // 移動左邊窗口將 window 縮小
            left++;
            // 進行 window 內資料更新
            ...
        }
    }
}
  • 什麼時候需要縮減 window 通常是解這類問題的關鍵。
    滿足可以將 window 縮減的條件,同時也代表目前應該暫停加入新元素,若 window 再繼續加入新元素的話,將會違反題目的要求,先透過縮減 window 以便讓新元素可以加入 window ,如果縮減 window 條件還滿足,就必須持續縮減左邊 window ,縮減左邊 window 也代表第一個指標需要往前進。
  • 程式碼中有兩個進行 window 內資料更新的區塊,等你開始套用後,會發現這兩塊區塊的動作具有對稱性。
  • 第二個指標需要依序往前,以便讓 window 擴大,在上面框架中,while 迴圈內執行 right++ 這個動作來擴大 window,也可以透過 for ( right = 0; right < parent.size(); right++) 來替代。

Leetcode #567 Permutation in String

回到前面舉的例題,將框架套用到 Leetcode #567 上。

首先探討 window needs shrink 的條件,這題要尋找是否包含 s1 這個子字串,s1 這個子字串內元素可以任意排列,但是對應的個數一定會一樣,可以理解為 window 的長度大小一定會跟 s1 的長度一樣。

因此縮減 window 的條件我們設定為 window 長度等於 s1 字串長度,當長度符合,但對應元素沒有找齊,這時候就應該縮減 window ,繼續滑動 window 來加入剩下的元素。

決定好 window needs shrink 條件後,剩下部份就是將 window 更新的區塊寫清楚即可。

bool checkInclusion(string s1, string s2) {
    unordered_map<char, int> need, window;
    for (char c : s1)
        need[c]++;
    int valid = 0;
    int left = 0, right = 0;
    while (right < s2.size())
    {
        char new_node = s2[right];
        if (need.count(new_node))
        {
            window[new_node]++;
            if (window[new_node] == need[new_node])
                valid++;
        }
        right++;

        while (right-left >= s1.size())
        {
            if (valid == need.size())
                return true;
            char remove_node = s2[left];
            left++;
            if (need.count(remove_node))
            {
                if(window[remove_node] == need[remove_node])
                    valid--;
                window[remove_node]--;
            }
        }
    }
    return false;
}

Leetcode #003 Longest Substring Without Repeating Characters

題目描述:

Given a string s, find the length of the longest substring without repeating characters.

看完題目可以歸納以想法

  • window 並不是固定的,而是要想辦法找到最長的 window 。
  • 此題並沒有目標 string ,因此框架中的 need 是不需要的

接下來必須訂下 window needs shrink 的條件,我們要找的 window 如果包含了重複字元,代表需要將左邊 window 縮減,必須不斷縮減直到沒有包含重複字元,這也是這題最困難的點。

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;
    int left = 0;
    int result = 0;
    for (int right=0; right<s.size(); right++)
    {
        char input = s[right];
        window[input]++;
        while (window[input] > 1)
        {
            char remove = s[left];
            window[remove]--;
            left++;
        }
        result = std::max (result, right-left+1);
    }
    return result;
}

Leetcode #424 Longest Repeating Character Replacement

這題困難點也在於該如何定義何時需要縮減 window ,題目給了 k 次機會可以替換字元,需找出最長字串只含單一字母,也就是整個 window 內除了某個字元以外,其他都會被替換。

當 window 長度減掉最常見字元的出現次數後,這個結果比 k 還大,代表 window 內條件已經不符合,需要縮減 window 了。

最常見字元的出現次數則是每次增加新字元到 window 時,再進行更新即可。

int characterReplacement(string s, int k) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    int max_char_cnt = 0;
    int result = 0;

    while (right < s.size())
    {
        char input = s[right];
        window[input]++;
        if (window[input] > max_char_cnt)
        {
            max_char_cnt = window[input];
        }
        right++;

        while (right-left - max_char_cnt > k)
        {
            char output = s[left];
            window[output]--;

            left++;
        }

        result = max(result, right-left);
    }
    return result;
}
  • 相似題目 Leetcode #1004

總結

Sliding Window 技巧有效減少不必要的 iteration , 進而降低時間複雜度,這樣題目的難度在於兩個部份:

  1. 決定何時該縮減 window ,也等同於決定何時應該停止增長 window ,只有當縮減 window 的條件不再成立,才能向右增長 window 。
  2. 在 submit 前需要思考許多細節問題。例如長度如何計算? 何時更新相關資料?

參考資料

  1. An Introduction to Sliding Window Algorithms
  2. 14 Patterns to Ace Any Coding Interview Question - hackernoon
  3. 滑动窗口技巧 - labuladong

Updated on 2021/01/31