This tutorial is a part of the Data Structures and Algorithms class:
- A typical problem solved by Sliding Window algorithm
- Characteristics of problems can be solved by Sliding Window
- Summary
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).
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) |
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
- How does Sliding Window solve problems?
- What kind of problems can typically be solved by Sliding Window?
- Recalculate the Complexity of the two problems above.
- Redo the two problems above. You should be able to quickly explain how the algorithm works and implement each of them within 10 mins.
- (Easy) Leetcode #1984. Minimum Difference Between Highest and Lowest of K Scores
- (Easy) Leetcode #643. Maximum Average Subarray I
- (Easy) Leetcode #485. Max Consecutive Ones
- (Easy) Leetcode #1763. Longest Nice Substring
- (Easy) Leetcode #2269. Find the K-Beauty of a Number
- (Easy) Leetcode #219. Contains Duplicate II
- (Medium) Leetcode #567. Permutation in String
- (Medium) Leetcode #1004. Max Consecutive Ones III
- (Medium) Leetcode #2024. Maximize the Confusion of an Exam
- More on Leetcode #sliding-window.