Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
As discussed below here is the solution similar to that in example but with if i...

Viacheslav Lushchinskiy

Oct 27, 2022

As discussed below here is the solution similar to that in example but with if instead of while

const f = (_str, _k) => { let windowStart = 0; const maxArray = []; const charFrequency = {};

for (let windowEnd = 0; windowEnd < _str.length; windowEnd++) { const rightChar = _str[windowEnd]; maxArray.push(rightChar);

if (!(rightChar in charFrequency)) { charFrequency[rightChar] = 0; } charFrequency[rightChar] += 1;

if (Object.keys(charFrequency).length > _k) { maxArray.shift(); // removes the first element in the Array const leftChar = _str[windowStart]; charFrequency[leftChar] -= 1; if (charFrequency[leftChar] === 0) { delete charFrequency[leftChar]; } windowStart += 1; } } return maxArray.length; };

0

0

Comments
Comments
V
Viacheslav Lushchinskiy3 years ago

Another question is about the methods like: "rightChar in charFrequency" or "maxArray.includes" in my previous example. Are they not considered as searches with its own O complexity that adds to the overall algorism complexity?

Design Gurus
Design Gurus3 years ago

This algorithm is correct. It will work with an 'if'.

If you put a 'while' that would work too and arguably faster.

Overall, the while loop will not run more than 'n' times for ALL iterations of the 'for' loop. This can also be inferred from 'windowStart += 1;' since...

On this page