Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 3: Smallest Window containing Substring (hard)

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!
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