Sliding Window

The sliding window technique can be applied to Strings and Arrays. It helps to solve the problem with O(n) time complexity otherwise will take O(n^2) or O(n^3).

The space complexity could be O(n) .There would be one more data structure generally to hold the data in a given window.

There are two types of sliding windows:

• Fixed-size sliding window

• Variable Size sliding window

References:

• https://leetcode.com/discuss/study-guide/1773891/Sliding-Window-Technique-and-Question-Bank → Contains good set of problems for practice

• https://leetcode.com/problems/permutation-in-string/solutions/1500902/java-tc-o-s2-sc-o-1-constant-space-sliding-window-solution/ --> OK OK resource. Contains few solutions in sliding window

• https://leetcode.com/discuss/general-discussion/1122776/summary-of-sliding-window-patterns-for-subarray-substring --> Very good resource helps build intuition on when and where to apply sliding window

• https://www.youtube.com/watch?v=MK-NZ4hN7rs --> Mental model of sliding window

• Sliding Window algorithm template to solve all the Leetcode substring search problem