Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Problem Challenge 3: 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!
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

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

nrstnbr

· 4 years ago

I feel this problem needs another example such as: s="ab", p="a"

This additional example makes it clear that you can't always create a sliding window to the end of the array and shrink from the beginning of the array.

I tried my solution in leetcode and it failed on this exact example but 100% would've worked on the examples you have here.

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. Correct me if i am wrong.

Show 1 reply
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.

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.