Sliding Window algorithm

This tutorial is a part of the Data Structures and Algorithms class:

A typical problem solved by Sliding Window algorithm

  • A window: is composed of consecutive elements (of array, string, ...).
  • The window gives access to multiple elements at the same time.
  • The window's size: can be fixed or varies, depending on how many data points we need.
  • Sliding: the window slides along with a pointer (of a FOR LOOP for example).

fixed sliding window

lecture-25/count-good-substrings.js
// count number of substrings that has 3 unique characters

var countGoodSubstrings = (s) => {
  const goodSubStrings = []

  for(let i = 0; i < s.length - 2; i++) {
    const set = new Set([s[i], s[i+1], s[i+2]]) // set of unique chars
    if(set.size === 3) { // if set has 3 unique chars
      goodSubStrings.push(s[i] + s[i+1] + s[i+2]) // substring had 3 distinct chars
    }
  }

  console.log('original string:', s)
  console.log('good substrings:', goodSubStrings)
  console.log('unique good substrings:', new Set(goodSubStrings))
  
  return new Set(goodSubStrings).size
}

console.log('good substrings count:', countGoodSubstrings('xyzzaz')) // 1
console.log('======================')
console.log('good substrings count:', countGoodSubstrings('bdakjijcoeedddadfelldbda')) // 11
$ node count-good-substrings.js
original string: xyzzaz
good substrings: [ 'xyz' ]
unique good substrings: Set { 'xyz' }
good substrings count: 1
======================
original string: bdakjijcoeedddadfelldbda
good substrings: [
  'bda', 'dak', 'akj',
  'kji', 'ijc', 'jco',
  'coe', 'adf', 'dfe',
  'fel', 'ldb', 'bda'
]
unique good substrings: Set {
  'bda',
  'dak',
  'akj',
  'kji',
  'ijc',
  'jco',
  'coe',
  'adf',
  'dfe',
  'fel',
  'ldb'
}
good substrings count: 11

Characteristics of problems can be solved by Sliding Window

Problem Input characteristics Algorithm Time
Complexity
Accessing a few consecutive data points at the same time is necessary/useful - usually array or string Slding Window O(n)

flexible sliding window

lecture-25/longest-sub-string.js
// count the number of chars of the longest substring of unique characters

var lengthOfLongestSubstring = function(s) {
  console.log('original:', s)

  let longestSubStrLen = 0 // hold max length substring
  let str = '' // current unique char substring
  let seen = new Set() // unique chars of current substring
  
  for(let i = 0; i < s.length; i++) {
    if(!seen.has(s[i])) { // new char is NOT in current substring
      str = str + s[i] // add new char to substring
      seen.add(s[i]) // now seen it
      longestSubStrLen = Math.max(longestSubStrLen, str.length) // recal max len
    } else { // new char is IN current substring
      str = str.substring(str.indexOf(s[i]) + 1) + s[i] // update unique substring
      seen = new Set(str.split('')) // update unique chars in substring
    }

    console.log('str:', str)
  }
  
  return longestSubStrLen
}

console.log('longest substr:', lengthOfLongestSubstring('abcabcbb')) // 3
console.log('================')
console.log('longest substr:', lengthOfLongestSubstring('aab')) // 2
$ node longest-sub-string.js
original: abcabcbb
str: a
str: ab
str: abc
str: bca
str: cab
str: abc
str: cb
str: b
longest substr: 3
================
original: aab
str: a
str: a
str: ab
longest substr: 2

Summary

Prob. class P. sub-class Input characteristics Algorithm Time
Complexity
(almost) ANY problem class array, matrix, ... Brute Force O(n) & up
Can try with any problem type - pass split test
- array, string or graph, ...
- divide, solve, combine gives a possible solution
Divide and Conquer O(nlogn)
- accessing 2 data points at a time is useful
- closing in the pointers proven to give a correct answer
- usually array or string
Two Pointers O(n)
1. Maximization
2. Minimization
array, string or graph, ... Greedy choice,
no guarantee for most optimal solution
varies
3. Find all options array, matrix, ... Brute Force O(n) & up
4. Find most optimal solution
5. Find a truth search for a number - sorted array
or balanced BST
Binary Search O(logn)
accessing a few consecutive data points at the same time is necessary/useful - usually array or string Slding Window O(n)

Real life interview questions

  1. How does Sliding Window solve problems?
  2. What kind of problems can typically be solved by Sliding Window?
  3. Recalculate the Complexity of the two problems above.
  4. Redo the two problems above. You should be able to quickly explain how the algorithm works and implement each of them within 10 mins.
  5. (Easy) Leetcode #1984. Minimum Difference Between Highest and Lowest of K Scores
  6. (Easy) Leetcode #643. Maximum Average Subarray I
  7. (Easy) Leetcode #485. Max Consecutive Ones
  8. (Easy) Leetcode #1763. Longest Nice Substring
  9. (Easy) Leetcode #2269. Find the K-Beauty of a Number
  10. (Easy) Leetcode #219. Contains Duplicate II
  11. (Medium) Leetcode #567. Permutation in String
  12. (Medium) Leetcode #1004. Max Consecutive Ones III
  13. (Medium) Leetcode #2024. Maximize the Confusion of an Exam
  14. More on Leetcode #sliding-window.