Sliding Window – 陪你刷題

何謂 sliding window？
sliding window 適用於線性資料結構，可以用來解決在線性資料結構中找到滿足特定條件的 sub-sequence 或 sub-array的問題。

sliding window 有以下特點：
1. 在線性時間內完成
2. 利用 two pointer 來控制 window 大小
3. 答案是連續的資料

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

何謂 sliding window

sliding window 適用於線性資料結構，線性資料結構是可以循序存取 (sequential access)的資料結構，例如 array, linked list 或 string ，sliding window 可以用來解決在線性資料結構中找到滿足特定條件的 sub-sequence 或 sub-array的問題，sliding window 有以下特點：

  1. 在線性時間內完成
  2. 利用 two pointer 來控制 window 大小
  3. 答案是連續的資料

直接先來看 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 用來紀錄目標字串包含的字元與對應的個數
     * window 用來記錄 sliding window 內資料
     */
    unordered_map<char, int> need, window;
    for (char c:child) need[c]++;

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

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

Leetcode #567 Permutation in String

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

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

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

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

// s1 為目標字串, s2 為被搜尋字串
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++;
            if (valid == need.size())
                return true;
        }
        right++;

        while (right-left >= s1.size())
        {
            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

找出最長的子字串，其中除了出現次數最多的字元外，最多只能包含 k 個非出現次數最多的字元。

使用 hash table 來記錄每個字元的出現次數。每次遇到新字元時，如果該字元的出現次數超過了目前出現次數最多的字元的出現次數，那麼就更新出現次數最多的字元。

這題的難點在於如何縮減 window。當 window 的長度減去出現次數最多的字元的出現次數後，如果剩餘的字元數大於 k，那麼就需要縮減 window。

縮減 window 時，不需要更新出現次數最多的字元的出現次數，因為 s[right] 必定不是 "出現次數最多的字元" ，才會需要去縮減 window ，所以縮減 window 並不會讓出現次數最多的字元的出現次數增加，以至於影響最長子字串長度。

即便因為縮減 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
  4. Sliding Window algorithm template to solve all the Leetcode substring search problem.

Updated on 2023-09-24 14:36:40 星期日

在〈Sliding Window – 陪你刷題〉中有 2 則留言

  1. 自動引用通知: Two Pointer 左右指標篇 – 陪你刷題 – haogroot's Blog
  2. 自動引用通知: Two Pointer 快慢指標篇 – 陪你刷題 – haogroot's Blog

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *