Sliding Window: 常用來解決字串問題

Sliding Window 通過不斷調整子序列的 start & end 位置，獲取滿足要求解

Sliding Window 可以算是廣義的左右指標中的一種，但是在某些情況下，Sliding Window 可以只使用一個 point 與 一個 window size 來實作，並不用真正使用到兩個指標。

左右指標 (反向指標) 可見 Two Pointer: 低空間複雜度的解題技巧一文

一般來說若給定的資料是線性結構，例如 array, linked list 或 string 等可以循序存取 (sequential access)，而題目要求找出滿足特定條件的最長/最短的字串、陣列或一個目標值，常可以使用 Sliding Window。

圖片來源: Interview Guide Series — Sliding Window

Sliding Window 特性

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

Sliding Window 常見題目

• 3. Longest Substring Without Repeating Characters

// BEST
function lengthOfLongestSubstring(s) {
    const set = new Set()
    let start = 0, length = 0
    for (let end = 0; end < s.length; end++) {
        while (set.has(s[end])) set.delete(s[start]), start++
        set.add(s[end])
        length = Math.max(length, set.size)
    }
    return length
}

lengthOfLongestSubstring('bbs') // 2
/*
end=0,set=[b  ],length=1
end=1,set=[   ],length=1
end=1,set=[b  ],length=1
end=2,set=[b,s],length=1
end=2,set=[b,s],length=2
*/

• 76. Minimum Window Substring
• 209. Minimum Size Subarray Sum
• 567. Permutation in String

參考資料
1. Sliding Window – 陪你刷題
2. Two Pointer 與Sliding Window
3. Leetcode 刷題 pattern - Sliding Window
4. 滑動視窗（Sliding Window）演算法介紹
5. Reliable Transmission - Sliding Window Algorithm
6. 【演演算法】滑動視窗三步走
7. Leetcode 必备算法：聊聊滑动窗口