Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Longest Substring with K Distinct Characters

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class Solution:
  def findLength(self, text, k):
      max_length = float('-inf')
      freq = {}
      j = 0
      
      for i in range(len(text)):
        freq[text[i]] = freq.get(text[i], 0)
        freq[text[i]] += 1 
        if len(freq) <= k:
          max_length = max(max_length, i - j + 1)
        else:
          while len(freq) > k:
            freq[text[j]] -= 1 
            if freq[text[j]] == 0:
              del freq[text[j]]
            j += 1
          
      return max_length
A

Anonymous

· 2 years ago

The current solution uses while(Object.keys()) which increases the time complexity from O(N) to O(N * K) where K is each key in the object that has to be added again into an array for each iteration.

The optimal solution would instead have an int as the counter which gets us back to O(N).

A

Anonymous

· 3 years ago

First of all, If you add a else condition for adding the characters to hashmap, you encounter an error which doesn't make sense, and second why do you initialize the char frequency to a 0 instead of a 1

Show 1 reply
A

Anonymous

· 3 years ago

Using set will make code more cleaner

A

Anonymous

· 4 years ago

This is one that is causing me a lot of trouble https://leetcode.com/problems/sliding-window-maximum/

Show 1 reply
A

Anonymous

· 4 years ago

I didn't really get the window " In the current window, ...." . Can anyone explain that? Tks in advance.

Show 1 reply
A

Anonymous

· 4 years ago

I believe I accounted for the edge cases... As long as you encounter a letter you've seen before, make the window start = window end since you will only be caring about a substring with no duplicates. Image

A

Anonymous

· 4 years ago

Can someone give me some feedback on this?

Image

Show 1 reply
A

Anonymous

· 4 years ago

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; };

Show 2 replies
A

Anonymous

· 4 years ago

I would like add two point.

  1. The while loop is not necessary, because we are asked for longest substring, so we do not have to waist CPU to shrink the string or array in the next task on more than 1 element. So if statement with just one iteration is enough
  2. In JS you can make use of Set data structure, that is more elegant as HashMap.

const func = (_str, _k) => { let result = []; let windowStart = 0; let setUnique = new Set() // Set keeps only uniq elements

for (let windowEnd = 0; windowEnd < _str.length; windowEnd++) { const _arr = [..._str] // transform string to array result.push(_arr[windowEnd]) setUnique.add(_arr[windowEnd])

if (setUnique.size > _k) { result.shift(); setUnique.delete(_arr[windowStart]) windowStart += 1; } } return result.length; };

Show 4 replies

Reading Progress

0%

Vote for new content