Minimum Window Substring in DSA Javascript - 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, and you want to find the shortest piece of the first string that has every letter from the second string. This helps in searching and matching tasks where you want to find a compact match.

Why it matters

Without this concept, searching for the smallest matching part in text would be slow and inefficient. It solves the problem of quickly finding the shortest segment that contains all needed characters, which is useful in text processing, DNA sequencing, and search engines. Without it, many applications would waste time scanning large texts unnecessarily.

Where it fits

Before learning this, you should understand basic string operations and the sliding window technique. After this, you can explore more complex substring problems, pattern matching algorithms, and optimization techniques in string processing.

Mental Model

Core Idea

Find the smallest window in a string that contains all characters of another string by expanding and shrinking a sliding window while tracking character counts.

Think of it like...

It's like trying to find the shortest stretch of road on a map that passes through all the cities you want to visit, moving forward to include cities and then backtracking to shorten the route without missing any city.

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

Window moves:
[Start] -> Expand right to include B, A, C
Window: A B C D E B A C
          ↑       ↑
          left    right

Shrink from left to find smallest window containing B, A, C

Final window: B A C
Positions: 5 to 7

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the problem asks: find the smallest substring containing all characters of another string.

Given two strings, source and target, we want to find the shortest part of source that has every character from target at least as many times as it appears in target. For example, if target is 'ABC', the substring must have at least one 'A', one 'B', and one 'C'.

Result

Clear understanding of the problem goal and what counts as a valid substring.

Understanding the problem precisely is key to choosing the right approach and avoiding confusion about what counts as a valid answer.

2

Foundation

Basic Sliding Window Technique

Concept: Introduce the sliding window method to scan substrings efficiently without checking all possibilities.

A sliding window uses two pointers (left and right) to represent a current substring. We move the right pointer to expand the window and include more characters, and move the left pointer to shrink it. This avoids checking every substring from scratch.

Result

Ability to represent and move over substrings efficiently using two pointers.

Sliding window reduces time complexity drastically by reusing previous work instead of restarting checks for every substring.

3

Intermediate

Tracking Character Counts with Hash Maps

Concept: Use hash maps (objects) to count characters needed and found in the current window.

Create a map for target characters with their required counts. As the window expands, count characters found. When the window has all required characters in needed amounts, try shrinking it to find smaller valid windows.

Result

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

Tracking counts precisely allows us to know exactly when the window is valid and when it can be shrunk safely.

4

Intermediate

Expanding and Shrinking Window Logic

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

Concept: Learn when and how to move left and right pointers to find the minimum window.

Expand the right pointer to include characters until the window is valid (contains all target chars). Then move the left pointer forward to remove unnecessary characters and shorten the window. Repeat until the right pointer reaches the end.

Result

A process to find the smallest valid window by balancing expansion and contraction.

Knowing when to shrink the window prevents missing smaller valid substrings and improves efficiency.

5

Intermediate

Handling Edge Cases and Multiple Occurrences

🤔Before reading on: do you think the window must contain characters in the same order as target? Commit to yes or no.

Concept: Understand that order does not matter, but counts do, and handle repeated characters correctly.

The window can have characters in any order. If target has repeated characters, the window must have at least that many. For example, if target is 'AABC', window must have two 'A's, one 'B', and one 'C'.

Result

Correct handling of repeated characters and ignoring order in the window.

Recognizing that order is irrelevant but counts matter avoids incorrect solutions and missed matches.

6

Advanced

Optimizing with Character Frequency and Match Count

🤔Before reading on: do you think checking all characters in the window every time is efficient? Commit to yes or no.

Concept: Use a match count to track how many target characters are fully matched to avoid scanning the whole window repeatedly.

Keep a count of how many unique characters have met their required frequency in the window. When this count equals the number of unique characters in target, the window is valid. This avoids checking all characters every time.

Result

Improved efficiency by reducing repeated checks and speeding up the algorithm.

Tracking match count is a key optimization that makes the solution scalable for large inputs.

7

Expert

JavaScript Implementation with Clear Annotations

🤔Before reading on: do you think the code should handle empty strings and no possible windows? Commit to yes or no.

Concept: See a complete, runnable JavaScript code example implementing the minimum window substring solution with comments.

const minWindow = (s, t) => { if (t.length === 0 || s.length === 0) return ""; const need = new Map(); for (const char of t) { need.set(char, (need.get(char) || 0) + 1); } let left = 0, right = 0; let required = need.size; let formed = 0; const windowCounts = new Map(); let minLen = Infinity; let minLeft = 0; while (right < s.length) { const c = s[right]; windowCounts.set(c, (windowCounts.get(c) || 0) + 1); if (need.has(c) && windowCounts.get(c) === need.get(c)) { formed++; } while (left <= right && formed === required) { if (right - left + 1 < minLen) { minLen = right - left + 1; minLeft = left; } const leftChar = s[left]; windowCounts.set(leftChar, windowCounts.get(leftChar) - 1); if (need.has(leftChar) && windowCounts.get(leftChar) < need.get(leftChar)) { formed--; } left++; } right++; } return minLen === Infinity ? "" : s.substring(minLeft, minLeft + minLen); }; // Example usage: console.log(minWindow("ADOBECODEBANC", "ABC")); // Output: "BANC"

Result

"BANC" is printed, the smallest substring containing 'A', 'B', and 'C'.

Seeing a full implementation clarifies how all concepts combine and handles edge cases like empty strings and no valid window.

Under the Hood

The algorithm uses two pointers to create a window over the source string. It keeps track of character counts needed and found using hash maps. When the window contains all required characters, it tries to shrink from the left to find the smallest valid window. Internally, this avoids checking all substrings by reusing counts and only updating when pointers move.

Why designed this way?

This approach was designed to reduce the brute force O(n^2) or worse complexity of checking all substrings. Using a sliding window with hash maps and a match count allows linear time complexity on average. Alternatives like checking every substring were too slow for large inputs.

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

Window pointers:
Left -> [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Right-> [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Process:
Expand right pointer -> include chars
Check counts -> if valid, try shrink left pointer
Update minimum window if smaller
Repeat until right reaches end

Myth Busters - 3 Common Misconceptions

Quick: Do you think the minimum window substring must have characters in the same order as the target string? Commit to yes or no.

Common Belief: The substring must have characters in the exact order as the target string.

Reality: The substring can have characters in any order as long as all required characters appear with correct counts.

Why it matters: Believing order matters leads to incorrect solutions and missed valid substrings.

Quick: Do you think the window must contain only the target characters and no others? Commit to yes or no.

Common Belief: The window should contain only the characters from the target string, no extras.

Reality: The window can contain extra characters; only the presence and count of target characters matter.

Why it matters: Trying to exclude extra characters complicates the solution unnecessarily and can cause failure to find valid windows.

Quick: Do you think checking the entire window for validity every time is efficient? Commit to yes or no.

Common Belief: We must check all characters in the window every time the window changes to see if it is valid.

Reality: Using a match count to track how many characters meet requirements avoids repeated full checks, improving efficiency.

Why it matters: Not optimizing this leads to slower algorithms that don't scale well with large inputs.

Expert Zone

1

The order of shrinking and expanding the window affects performance and correctness; shrinking too early or late can miss minimal windows.

2

Using a map for counts allows handling Unicode or extended character sets beyond ASCII easily.

3

Tracking only the count of fully matched characters (formed) instead of scanning the whole map each time is a subtle but critical optimization.

When NOT to use

If the problem requires substrings with characters in a specific order or with gaps, this approach is not suitable. Instead, use pattern matching algorithms like KMP or dynamic programming. Also, for very large alphabets with sparse matches, specialized data structures like suffix trees may be better.

Production Patterns

In real systems, this pattern is used in search engines to find snippets containing all query terms, in bioinformatics to find DNA segments with specific markers, and in text editors for highlighting minimal matches. It is often combined with caching and incremental updates for performance.

Connections

Sliding Window Technique

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

Mastering this problem deepens understanding of sliding windows, which appear in many string and array problems.

Hash Maps

Uses hash maps to count and track characters efficiently.

Knowing how to use hash maps for frequency counting is essential for many algorithms involving character or element counts.

Supply Chain Management

Both involve tracking required items and adjusting inventory or window size to meet demands efficiently.

Understanding how to balance supply and demand in logistics helps grasp the idea of expanding and shrinking windows to meet character requirements.

Common Pitfalls

#1 Not updating the formed count when shrinking the window.

Wrong approach:

windowCounts.set(leftChar, windowCounts.get(leftChar) - 1);
// Missing formed-- when count falls below needed

Correct approach:

windowCounts.set(leftChar, windowCounts.get(leftChar) - 1);
if (need.has(leftChar) && windowCounts.get(leftChar) < need.get(leftChar)) {
formed--;
}

Root cause:

Forgetting to track when the window no longer satisfies the required counts leads to incorrect validity checks.

#2 Returning the first valid window instead of the minimum one.

Wrong approach:

Return substring as soon as formed === required without trying to shrink window.

Correct approach:

Continue shrinking the window from the left while it remains valid to find the smallest window.

Root cause:

Misunderstanding that the first valid window is not necessarily the smallest causes suboptimal results.

#3 Not handling empty strings or no possible window cases.

Wrong approach:

No checks for empty input or returning undefined when no window found.

Correct approach:

if (t.length === 0 || s.length === 0) return "";
// Return empty string if no valid window found

Root cause:

Ignoring edge cases leads to runtime errors or incorrect outputs.

Key Takeaways

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

Tracking character counts with hash maps and a match count allows efficient checking of window validity.

Expanding the window to include needed characters and shrinking it to minimize size is the core process.

Order of characters in the window does not matter, only presence and count do.

Optimizations like tracking formed matches and handling edge cases are essential for a robust solution.

Practice

1. What does the "Minimum Window Substring" problem ask you to find given two strings s and t?

easy

A. The number of times t appears in s

B. The longest substring in s that does not contain any character from t

C. The smallest substring in s that contains all characters of t

D. The substring of s that is exactly equal to t

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the smallest part of string s that has all characters from string t, including duplicates.

2. Step 2: Compare options with the problem statement

   The smallest substring in s that contains all characters of t matches this goal exactly. Other options describe different problems.

3. Final Answer:

   The smallest substring in s that contains all characters of t -> Option C

4. Quick Check:

   Minimum Window Substring = smallest substring with all chars [OK]

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

Common Mistakes:

• Confusing longest substring with smallest
• Ignoring duplicate characters in t
• Thinking it counts occurrences instead of substring

2. Which of the following JavaScript code snippets correctly initializes a frequency map for characters in string t?

easy

A. const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; }

B. const freq = new Map(); for (const char of t) { freq.set(char, freq.get(char) + 1); }

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

D. const freq = []; for (const char of t) { freq[char] += 1; }

Solution

1. Step 1: Check initialization and increment logic

   const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; } initializes an empty object and increments counts safely using freq[char] = (freq[char] || 0) + 1, which works even if freq[char] is undefined.

2. Step 2: Identify errors in other options

   const freq = new Map(); for (const char of t) { freq.set(char, freq.get(char) + 1); } tries to use Map but calls freq.get(char) + 1 without checking if freq.get(char) is undefined, causing NaN. const freq = {}; for (let i = 0; i < t.length; i++) { freq[t[i]] = freq[t[i]] + 1; } tries to add 1 to undefined without default. const freq = []; for (const char of t) { freq[char] += 1; } uses an array but accesses with string keys, which is invalid.

3. Final Answer:

   const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; } -> Option A

4. Quick Check:

   Safe frequency map init = const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; } [OK]

Hint: Use (freq[char] || 0) + 1 to safely count chars [OK]

Common Mistakes:

• Not initializing counts before adding
• Using Map without checking undefined values
• Using array with string keys

3. What will be the output of the following JavaScript code snippet?

const s = "ADOBECODEBANC";
const t = "ABC";

function minWindow(s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  let left = 0, right = 0, count = t.length;
  let minLen = Infinity, start = 0;

  while (right < s.length) {
    if (need[s[right]] > 0) count--;
    need[s[right]] = (need[s[right]] || 0) - 1;
    right++;

    while (count === 0) {
      if (right - left < minLen) {
        minLen = right - left;
        start = left;
      }
      need[s[left]]++;
      if (need[s[left]] > 0) count++;
      left++;
    }
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

console.log(minWindow(s, t));

medium

A. "DOBECODEBA"

B. "ADOBEC"

C. "CODEBA"

D. "BANC"

Solution

1. Step 1: Understand the sliding window logic

   The code uses two pointers expanding and shrinking a window over s. It tracks needed characters from t and shrinks window when all are found.

2. Step 2: Trace the window to find minimum substring

   For s = "ADOBECODEBANC" and t = "ABC", the smallest substring containing all chars is "BANC" starting at index 9 with length 4.

3. Final Answer:

   "BANC" -> Option D

4. Quick Check:

   Minimum window substring = "BANC" [OK]

Hint: Trace sliding window to find smallest valid substring [OK]

Common Mistakes:

• Confusing substring start and end indices
• Not updating minimum length correctly
• Ignoring character counts when shrinking window

4. Identify the bug in this JavaScript function for Minimum Window Substring:

function minWindow(s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  let left = 0, right = 0, count = t.length;
  let minLen = Infinity, start = 0;

  while (right < s.length) {
    if (need[s[right]] > 0) count--;
    need[s[right]]--;
    right++;

    while (count === 0) {
      if (right - left < minLen) {
        minLen = right - left;
        start = left;
      }
      need[s[left]]++;
      if (need[s[left]] > 0) count++;
      left++;
    }
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

medium

A. The count variable should be initialized to 0 instead of t.length

B. The decrement of need[s[right]] should use (need[s[right]] || 0) - 1 to avoid undefined

C. The inner while loop condition should be count > 0 instead of count === 0

D. The substring returned should use s.substring(start, right) instead of s.substring(start, start + minLen)

Solution

1. Step 1: Check how need map is updated

   The code does need[s[right]]-- without ensuring need[s[right]] is defined. If s[right] is not in t, need[s[right]] is undefined, causing NaN on decrement.

2. Step 2: Fix by defaulting undefined to 0 before decrement

   Use need[s[right]] = (need[s[right]] || 0) - 1 to avoid NaN and keep counts correct.

3. Final Answer:

   The decrement of need[s[right]] should use (need[s[right]] || 0) - 1 to avoid undefined -> Option B

4. Quick Check:

   Safe decrement with default 0 avoids NaN [OK]

Hint: Always default undefined to 0 before decrementing counts [OK]

Common Mistakes:

• Not handling characters not in t
• Wrong initialization of count variable
• Incorrect substring slicing

5. Given strings s = "aabbccdd" and t = "abc", what is the minimum window substring that contains all characters of t considering duplicates in t only once?

hard

A. "abbc"

B. "abc"

C. "aabbc"

D. "bcca"

Solution

1. Step 1: Understand character requirements from t

   String t = "abc" has characters 'a', 'b', 'c' each once. So the window must contain at least one 'a', one 'b', and one 'c'.

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

   In s = "aabbccdd", the substring "abc" starting at index 1 (characters at indices 1:'a', 2:'b', 3:'b', 4:'c') is not contiguous as "abc" is not directly present, but the smallest substring containing all characters once is actually "abc" starting at index 1 or 2. However, the substring "abc" is present starting at index 1 to 3 ("abb") is missing 'c', so the smallest substring containing all is "abc" at indices 1 to 3 is invalid. The substring "abbc" (indices 1 to 4) contains all characters and is minimal. But the substring "abc" (indices 1 to 3) is missing 'c'. The substring "abc" (indices 2 to 4) is "bbc" missing 'a'. The substring "abc" (indices 0 to 2) is "aab" missing 'c'. The substring "abc" (indices 3 to 5) is "bcc" missing 'a'. The substring "abc" (indices 1 to 4) is "abbc" which contains all. The substring "abc" (indices 1 to 3) is "abb" missing 'c'. The substring "abc" (indices 2 to 4) is "bbc" missing 'a'. The substring "abc" (indices 0 to 4) is "aabbc" which is longer. The substring "abc" (indices 1 to 4) "abbc" is the smallest substring containing all characters once. However, the option "abc" is present as "abc", but it is not a substring of s. So the correct minimal substring is "abbc".

3. Final Answer:

   "abbc" -> Option A

4. Quick Check:

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

Hint: Count chars in t once; find smallest substring covering them [OK]

Common Mistakes:

• Counting duplicates in t multiple times
• Choosing longer substrings unnecessarily
• Thinking it counts occurrences instead of substring