Grokking Meta Coding Interview

0% completed

​

Solution: Minimum Window Substring

Problem Statement

Given a string s and t of length m and n respectively, find the smallest substring in a given string 's' that contains all the characters (including duplicate) of another string 't'. The order of characters in 't' doesn't matter, but the substring in 's' must include all characters of 't', possibly with additional characters.

If no such substring exists, return an empty string.

Examples

Example 1:

  • Input: s = "xyyzyzyx", t = "xyz"
  • Expected Output: "zyx"

.....

.....

.....

Like the course? Get enrolled and start learning!
Nishith Iyer

Nishith Iyer

· 2 years ago

In the code we can see that, the map stores frequency of every character in string 's' while expanding the sliding window regardless of whether it is available in the string 't' or not. In cases where character occurrence isn't found in 't' the count will get negative.

We are putting characters from both strings 's' & 't' into the hash map wherein the former gets populated during window expansion and the latter gets populated early on at the start during initialisation.

Am I missing something here?