Minimum Window Substring in DSA Typescript - Deep Dive

Overview - Minimum Window Substring

What is it?

Minimum Window Substring is a problem where you find the smallest part of a string that contains all characters of another string. Imagine you have two strings: a big one and a smaller one. You want to find the shortest piece of the big string that has every letter from the smaller string, including duplicates.

Why it matters

This problem helps in searching and matching patterns efficiently, which is important in text processing, DNA sequencing, and search engines. Without this concept, finding such substrings would be slow and inefficient, making many applications sluggish or inaccurate.

Where it fits

Before this, you should understand basic string operations and sliding window technique. After mastering this, you can learn more complex pattern matching algorithms like KMP or Rabin-Karp, and advanced sliding window problems.

Mental Model

Core Idea

Find the smallest window in a big string that contains all characters of a smaller string by expanding and shrinking a sliding window.

Think of it like...

It's like trying to find the shortest segment of a long sentence that contains all the words from a shopping list, moving forward to include needed words and moving backward to drop extra words.

Big String:  A B C D E B A C
Target:       A B C

Sliding Window:
Start -> [A B C D E] <- End
Shrink from start to get minimum window containing A, B, C

Diagram:
┌─────────────────────────────┐
│ A │ B │ C │ D │ E │ B │ A │ C │
└─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┘
  ↑   ↑
 start end

Move end forward to include all chars, then move start forward to shrink window.

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the minimum window substring problem asks for and the inputs involved.

You have two strings: source (big string) and target (small string). The goal is to find the smallest substring in source that contains all characters from target, including duplicates. For example, source = 'ADOBECODEBANC', target = 'ABC', the answer is 'BANC'.

Result

Clear understanding of problem inputs and expected output.

Understanding the problem clearly is the first step to solving it efficiently.

2

Foundation

Basic Sliding Window Technique

Concept: Learn how to use two pointers to represent a window in a string and move them to explore substrings.

Use two pointers, start and end, initially at the beginning of the source string. Move end forward to expand the window and include more characters. Move start forward to shrink the window and remove characters. This technique helps explore all possible substrings efficiently.

Result

Ability to represent and move a window over a string.

Sliding window reduces the need to check all substrings by focusing on expanding and shrinking a range.

3

Intermediate

Tracking Character Counts with Maps

Concept: Use a map (dictionary) to count how many times each character in target must appear in the window.

Create a map for target characters with their required counts. As you move the window, keep track of how many required characters are currently in the window using another map. When the window contains all required characters with correct counts, it is a valid window.

Result

Ability to check if current window satisfies the target character requirements.

Counting characters precisely is key to knowing when a window is valid.

4

Intermediate

Expanding and Shrinking the Window

🤔Before reading on: Do you think we should shrink the window as soon as it contains all characters, or wait until the end pointer reaches the string's end? Commit to your answer.

Concept: Expand the window by moving end pointer until all target characters are included, then shrink from start to find the smallest valid window.

Move end pointer forward, adding characters to the window count. When window contains all target chars, move start pointer forward to remove extra chars and minimize window size. Keep track of the smallest window found.

Result

Finding the minimum length substring that contains all target characters.

Shrinking the window as soon as it is valid helps find the smallest possible substring.

5

Intermediate

Handling Duplicate Characters in Target

🤔Before reading on: Does the window need to contain each character only once, or as many times as it appears in the target? Commit to your answer.

Concept: The window must contain each character as many times as it appears in the target string, not just once.

If target has duplicates, like 'AABC', the window must have two 'A's, one 'B', and one 'C'. The count maps track these exact counts. The window is valid only when all counts meet or exceed target counts.

Result

Correctly handling targets with repeated characters.

Accounting for duplicates ensures the solution is accurate for all target strings.

6

Advanced

Optimizing with Character Frequency and Match Count

🤔Before reading on: Is it enough to check character counts every time, or can we track progress more efficiently? Commit to your answer.

Concept: Use a match count to track how many target characters are fully matched in the window, avoiding repeated full checks.

Keep a variable 'formed' that increases when a character's count in the window matches the target count. When 'formed' equals the number of unique characters in target, the window is valid. This avoids checking all counts repeatedly.

Result

More efficient checking of window validity.

Tracking progress incrementally reduces unnecessary work and speeds up the algorithm.

7

Expert

Handling Edge Cases and Performance Trade-offs

🤔Before reading on: Do you think the algorithm always runs in linear time? Commit to your answer.

Concept: Understand how the algorithm behaves with edge cases like empty strings, no valid window, and large inputs, and analyze its time complexity.

If target is empty or longer than source, return empty string immediately. If no valid window exists, return empty string. The algorithm runs in O(n) time because each character is visited at most twice (once by end and once by start). However, large character sets or inefficient data structures can affect performance.

Result

Robust and efficient implementation ready for production.

Knowing edge cases and complexity helps write reliable and performant code.

Under the Hood

The algorithm uses two pointers to create a sliding window over the source string. It maintains two maps: one for required character counts from the target, and one for current counts in the window. A variable tracks how many characters have met their required counts. The window expands by moving the end pointer until all required characters are included, then shrinks by moving the start pointer to find the smallest valid window. This process continues until the end pointer reaches the string's end.

Why designed this way?

This approach was designed to avoid checking all substrings, which would be very slow. By using a sliding window and counting characters, it reduces the problem from O(n^2) to O(n) time. The design balances simplicity and efficiency, using maps for flexible character sets and a match count to minimize repeated checks.

Source String:  A D O B E C O D E B A N C

Target Map:     {A:1, B:1, C:1}

Sliding Window:
┌─────────────────────────────┐
│ A │ D │ O │ B │ E │ C │ O │ D │ E │ B │ A │ N │ C │
└─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┘
  ↑   ↑
 start end

Process:
1. Expand end until window contains A,B,C
2. Shrink start to minimize window
3. Update minimum window if smaller
4. Repeat until end reaches string end

Myth Busters - 3 Common Misconceptions

Quick: Does the minimum window substring always start at the first occurrence of the first target character? Commit yes or no.

Common Belief: The minimum window substring always starts at the first occurrence of the first character in the target string.

Reality: The minimum window can start anywhere in the source string; it does not have to start at the first occurrence of any target character.

Why it matters: Assuming it starts at the first occurrence can cause missing smaller valid windows later in the string.

Quick: If the target has duplicate characters, is it enough to have one occurrence of each character in the window? Commit yes or no.

Common Belief: Having one occurrence of each character is enough, even if the target has duplicates.

Reality: The window must contain each character as many times as it appears in the target, including duplicates.

Why it matters: Ignoring duplicates leads to incorrect results, missing valid windows or returning invalid ones.

Quick: Does the sliding window algorithm always run in linear time regardless of input? Commit yes or no.

Common Belief: The sliding window algorithm always runs in O(n) time for any input.

Reality: While the algorithm is O(n) on average, large character sets or inefficient data structures can increase overhead, and worst-case scenarios may degrade performance.

Why it matters: Overlooking performance nuances can cause slowdowns in real-world applications with large or complex inputs.

Expert Zone

1

Tracking the 'formed' count precisely avoids repeated full map comparisons, significantly improving performance.

2

Using a hash map allows handling any character set, including Unicode, but may add overhead compared to fixed-size arrays for limited alphabets.

3

Shrinking the window only when valid ensures minimal windows are found without missing any smaller valid substring.

When NOT to use

If the target string is very large or the character set is extremely limited and fixed (like only lowercase letters), specialized algorithms or fixed-size arrays may be more efficient. For approximate matches or fuzzy searching, other algorithms like Levenshtein distance or regex matching are better.

Production Patterns

Used in search engines to find relevant snippets, in bioinformatics to locate DNA sequences, and in text editors for find-and-replace features. Often combined with caching and preprocessing for repeated queries.

Connections

Sliding Window Technique

Minimum Window Substring is a classic application of the sliding window technique.

Mastering this problem deepens understanding of sliding window, which is widely used in substring and subarray problems.

Hash Maps / Dictionaries

Uses hash maps to count and track characters efficiently.

Understanding hash maps helps manage character frequencies and speeds up membership checks.

Inventory Management

Both track quantities of items needed and available to fulfill a requirement.

Knowing how to balance supply and demand in inventory helps understand how the window balances required and current characters.

Common Pitfalls

#1 Not accounting for duplicate characters in the target string.

Wrong approach:

if (windowCount[char] >= 1) { // assume one occurrence is enough }

Correct approach:

if (windowCount[char] >= targetCount[char]) { // check exact required count }

Root cause:

Misunderstanding that each character must appear as many times as in the target, not just once.

#2 Shrinking the window before it contains all required characters.

Wrong approach:

while (window is not valid) { start++; } // shrinking too early

Correct approach:

while (window is valid) { start++; } // shrink only when valid

Root cause:

Confusing when to shrink the window, leading to missing valid substrings.

#3 Using inefficient data structures causing slow performance.

Wrong approach:

Using nested loops to check all substrings or using arrays for large character sets without hashing.

Correct approach:

Use hash maps and sliding window to achieve O(n) time complexity.

Root cause:

Not leveraging the sliding window technique and appropriate data structures.

Key Takeaways

Minimum Window Substring finds the smallest substring containing all characters of another string using a sliding window.

Using two pointers to expand and shrink the window efficiently explores all candidate substrings.

Tracking character counts with hash maps ensures the window meets the exact requirements, including duplicates.

Incremental tracking of matched characters avoids repeated full checks and improves performance.

Handling edge cases and understanding time complexity ensures robust and efficient solutions.

Practice

1. What is the main goal of the Minimum Window Substring problem?

easy

A. Sort characters of a string in ascending order

B. Find the smallest substring in a string that contains all characters of another string

C. Count the number of substrings containing a specific character

D. Find the longest substring without repeating characters

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the smallest part of a string that has all characters from another string.

2. Step 2: Identify the goal

   The goal is to find the minimum length substring that contains all required characters, not just any substring.

3. Final Answer:

   Find the smallest substring in a string that contains all characters of another string -> Option B

4. Quick Check:

   Minimum window substring = smallest substring with all chars [OK]

Hint: Look for smallest substring covering all target chars [OK]

Common Mistakes:

• Confusing with longest substring problems
• Ignoring the requirement to include all characters
• Thinking it's about sorting characters

2. Which of the following TypeScript code snippets correctly initializes a frequency map for characters in string t for the Minimum Window Substring problem?

easy

A. const freqMap = {}; for (let i = 0; i < t.length; i++) { freqMap[t[i]] = freqMap[t[i]] + 1; }

B. const freqMap = new Map(); for (const ch of t) { freqMap[ch] = freqMap[ch] + 1; }

C. const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1); }

D. const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, freqMap.get(ch) + 1); }

Solution

1. Step 1: Check correct Map usage in TypeScript

   const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1); } uses Map with get and set methods and handles undefined with nullish coalescing (?? 0).

2. Step 2: Identify errors in other options

   const freqMap = {}; for (let i = 0; i < t.length; i++) { freqMap[t[i]] = freqMap[t[i]] + 1; } uses object but does not initialize counts, causing NaN. const freqMap = new Map(); for (const ch of t) { freqMap[ch] = freqMap[ch] + 1; } uses Map but accesses like object property, which is incorrect. const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, freqMap.get(ch) + 1); } does not handle undefined before adding 1, causing NaN.

3. Final Answer:

   const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1); } -> Option C

4. Quick Check:

   Use Map.get with ?? 0 to avoid undefined [OK]

Hint: Use Map.get with ?? 0 to safely increment counts [OK]

Common Mistakes:

• Accessing Map like an object property
• Not initializing counts before increment
• Using object without initializing keys

3. What will be the output of the following TypeScript code snippet for s = "ADOBECODEBANC" and t = "ABC"?

function minWindow(s: string, t: string): string {
  const freqMap = new Map();
  for (const ch of t) freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1);
  let left = 0, right = 0, count = t.length, minLen = Infinity, start = 0;
  while (right < s.length) {
    const ch = s[right];
    if (freqMap.has(ch)) {
      freqMap.set(ch, freqMap.get(ch)! - 1);
      if (freqMap.get(ch)! >= 0) count--;
    }
    while (count === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        start = left;
      }
      const leftChar = s[left];
      if (freqMap.has(leftChar)) {
        freqMap.set(leftChar, freqMap.get(leftChar)! + 1);
        if (freqMap.get(leftChar)! > 0) count++;
      }
      left++;
    }
    right++;
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}
console.log(minWindow(s, t));

medium

A. "BANC"

B. "ADOBEC"

C. "CODEBA"

D. "DOBECODEBA"

Solution

1. Step 1: Understand the sliding window approach

   The code uses two pointers expanding and shrinking the window to find the smallest substring containing all chars of t.

2. Step 2: Trace the code with given input

   The minimum window substring containing A, B, and C in s = "ADOBECODEBANC" and t = "ABC" is "BANC".

3. Final Answer:

   "BANC" -> Option A

4. Quick Check:

   Minimum window substring for "ABC" in "ADOBECODEBANC" is "BANC" [OK]

Hint: Use sliding window to shrink when all chars matched [OK]

Common Mistakes:

• Returning first found substring instead of minimum
• Not updating minimum length correctly
• Incorrectly increasing count when shrinking window

4. Identify the bug in the following TypeScript code snippet for Minimum Window Substring and select the fix:

function minWindow(s: string, t: string): string {
  const freqMap = new Map();
  for (const ch of t) freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1);
  let left = 0, right = 0, count = t.length, minLen = Infinity, start = 0;
  while (right < s.length) {
    const ch = s[right];
    if (freqMap.has(ch)) {
      freqMap.set(ch, freqMap.get(ch)! - 1);
      if (freqMap.get(ch)! > 0) count--;
    }
    while (count === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        start = left;
      }
      const leftChar = s[left];
      if (freqMap.has(leftChar)) {
        freqMap.set(leftChar, freqMap.get(leftChar)! + 1);
        if (freqMap.get(leftChar)! > 0) count++;
      }
      left++;
    }
    right++;
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

medium

A. Change condition from if (freqMap.get(ch)! > 0) count--; to if (freqMap.get(ch)! >= 0) count--;

B. Initialize count with 0 instead of t.length

C. Remove the inner while loop

D. Change freqMap.set(ch, freqMap.get(ch)! - 1); to freqMap.set(ch, freqMap.get(ch)! + 1);

Solution

1. Step 1: Identify the condition for decreasing count

   The count should decrease when a needed character is found and its frequency is still >= 0, not > 0.

2. Step 2: Fix the condition

   Changing from > 0 to >= 0 ensures count decreases correctly when the character frequency reaches zero.

3. Final Answer:

   Change condition from if (freqMap.get(ch)! > 0) count--; to if (freqMap.get(ch)! >= 0) count--; -> Option A

4. Quick Check:

   Use >= 0 to count chars correctly [OK]

Hint: Use >= 0 when checking frequency to update count [OK]

Common Mistakes:

• Using > 0 causes missing valid matches
• Incorrect count initialization
• Removing inner loop breaks shrinking window

5. Given strings s = "aabbccdd" and t = "abc", which of the following substrings is the correct minimum window substring containing all characters of t? Consider that characters can appear multiple times in s but only once in t.

hard

A. "aabbc"

B. "abc"

C. "bcca"

D. "abbc"

Solution

1. Step 1: Understand character requirements

   String t requires one 'a', one 'b', and one 'c'. The substring must contain at least these once.

2. Step 2: Find smallest substring in s containing 'a', 'b', 'c'

   "abbc" contains 'a', 'b', 'b', 'c' and is length 4. "abc" does not appear as a contiguous substring in s. "bcca" and "aabbc" are longer substrings.

3. Final Answer:

   "abbc" -> Option D

4. Quick Check:

   Minimum window substring with all chars = "abbc" [OK]

Hint: Check substring length and character coverage carefully [OK]

Common Mistakes:

• Assuming "abc" substring exists exactly
• Ignoring repeated characters in s
• Choosing longer substrings unnecessarily