Skip to content

Instantly share code, notes, and snippets.

@sebringj
Last active April 9, 2021 19:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sebringj/001299309dd84a778be6d34b66367a44 to your computer and use it in GitHub Desktop.
Save sebringj/001299309dd84a778be6d34b66367a44 to your computer and use it in GitHub Desktop.
My sliding window algorithm
const contains = (str, t) => {
for (const c of t) {
if (!str.includes(c)) {
return false;
}
}
return true;
}
const findWindows = (size, s, t) => {
if (t.length > s.length || s.length < size) return [];
const windows = [];
for (let i = 0; i <= s.length - size; i++) {
const str = s.substr(i, size);
if (contains(str, t)) {
windows.push(str);
}
}
return windows;
}
const findAllWindows = (source, search, maxResults) => {
const s = source, t = search, k = maxResults;
const st = s.replace(/\s/g, '');
const min = t.length;
const max = st.length;
let windows = [];
for (let i = min; i <= max; i++) {
if (windows.length >= k) break;
const foundWindows = findWindows(i, st, t).filter(w => w.length > 0);
windows = windows.concat(foundWindows);
}
windows.sort((a,b) => {
return a.length < b.length;
});
return windows.slice(0, k);
}
@sebringj
Copy link
Author

sebringj commented Apr 9, 2021

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment