Grokking the Engineering Manager Coding Interview
Vote

0% completed

​

Solution: Smallest Window containing Substring

Problem Statement

Given a string and a pattern, find the smallest substring in the given string which has all the character occurrences of the given pattern.

Example 1:

Input: String="aabdec", Pattern="abc"  
Output: "abdec"  
Explanation: The smallest substring having all characters of the pattern is "abdec"

Example 2:

Input: String="aabdec", Pattern="abac"  
Output: "aabdec"  
Explanation: The smallest substring having all characters occurrences of the pattern is "aabdec"

Example 3:

Input: String="abdbca", Pattern="abc"

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from collections import Counter

class Solution:
  def findSubstring(self, text, pattern):
    
    counter_freq = Counter(pattern)
    text_freq = {}
    result = ""
    short_len = float('inf')
    
    # method that checks if text map contains the counter map 
    def found(text_freq, counter_freq):
      for char, freq in counter_freq.items():
        if char not in text_freq or freq > text_freq[char]:
          return False
      return True

    i = 0
    j = 0

    while i < len(text):
      # append i frequency to the text map and move i 
      text_freq[text[i]] = text_freq.get(text[i], 0)
      text_freq[text[i]] += 1
      i += 1

      # while we can find the pattern in the text
      while found(text_freq, counter_freq):
        # if we found shorter string that
V

Viktor

· 4 years ago

Hey, thanks for this course in general and for the good explanations. My question is: could we have just

if char_frequency[right_char] = 0

instead of

if char_frequency[right_char] >= 0

in Python example? To count only when we match all occurrences of a character.

Show 1 reply
A

Alan Ross

· 4 years ago

I don't understand the purpose of minLength? like it is the length of the entire string + 1, why is it called minLength? There's no explanation as to why it's called that and what it's used for.

Show 2 replies
B

Bharpur Singh

· 4 years ago

I don't think the reason why we need to check "if min_length > window_end - window_start + 1" in while loop and then update substr_start because everytime if matched == pattern's length then we have a valid pattern and we can shrink window and set the new start. Can we replace Option 1 with Option 2. Correct me if i am wrong.

B

Bharpur Singh

· 4 years ago

I don't think the reason why we need to check "if min_length > window_end - window_start + 1" in while loop and then update substr_start because everytime if matched == pattern's length then we have a valid pattern and we can shrink window and set the new start. Correct me if i am wrong.

Show 1 reply
J

John Moon

· 4 years ago

Hi, most of this makes sense besides the following line.

if (charFrequencyMap.get(leftChar) == 0)

We are searching for duplicate char's if we already matched on a char. However, shouldn't we be checking for -1?

E.G if we're looking for findSubstring("aabdec", "abc") example, after rightChar matching on "a" twice, the charFrequencyMap would return -1 for "a".

Why is it charFrequencyMap.get(leftChar) == 0 instead of charFrequencyMap.get(leftChar) < 0

Thank you

Show 1 reply
A

aj

· 4 years ago

I am also failing to understand the time complexity of the algo. I understand that creating the map is O(M) and the window for loop is O(N). How is total complexity O(N+M) because what about the inner while loop. Take this e.g. str = 'aaaaaabc', pattern = 'bc'. The while loop will run for a substantial time. In worst case of O(N-M) right? Then can we just ignore this altogether?

Show 6 replies
A

aj

· 4 years ago

if (charFrequencyMap.get(rightChar) >= 0) // count every matching of a character

the comment for this line mentions that every match of a character is counted i.e. matched is incremented but that isn't true is it. We won't count EVERY matching of a character. For 'aabdec' and 'abc'.. we will increment matched just for the 1st 'a' and NOT the second.

So the comment is a bit misleading imo.

G

Gideon

· 4 years ago

Hi everyone, is there any disadvantage to using the same conditions as the previous question?

That is, in order of the highlighted code we use these conditions:

  1. if (charFrequency[rightChar] == 0)
  2. while (matched === charFreqMap .size)

This works for the provided test cases, and on LeetCode.

I think the logic checks out because all we are doing is keeping track of if each character in the pattern is matched in the current window.

Show 8 replies
N

Nick

· 4 years ago

For anyone struggling understanding the provided solution, I suggest looking at Neetcode solve this. After watching his explanation this made a lot more sense utilizing just one hashmap

Reading Progress

0%