Minimum Window Substring in DSA Typescript - Build from Scratch

Minimum Window Substring

📖 Scenario: Imagine you are working on a text search tool. You want to find the smallest part of a document that contains all the keywords a user is searching for.

🎯 Goal: Build a program that finds the minimum window substring in a given string s that contains all characters of another string t.

📋 What You'll Learn

Create a string variable s with the value "ADOBECODEBANC".

Create a string variable t with the value "ABC".

Create a function minWindow that takes two strings s and t and returns the minimum window substring of s containing all characters of t.

Use a sliding window technique with two pointers left and right to find the minimum substring.

Print the result of minWindow(s, t).

💡 Why This Matters

🌍 Real World

Finding the smallest snippet in a document that contains all search keywords helps users quickly locate relevant information.

💼 Career

This technique is useful in search engines, text editors, and any software that needs efficient substring searching.

1

Create the input strings

Create a string variable called s with the value "ADOBECODEBANC" and a string variable called t with the value "ABC".

DSA Typescript

// Create string variables s and t with given values
// Your code here

Hint

Use const s: string = "ADOBECODEBANC"; and const t: string = "ABC";

2

Set up character frequency map for t

Create a constant called need that is a Map to count the frequency of each character in t. Also create a variable have initialized to 0 to track how many characters are matched, and a variable needCount set to the size of need.

DSA Typescript

const s: string = "ADOBECODEBANC";
const t: string = "ABC";
// Create a Map called need to count characters in t
// Create variables have and needCount
// Your code here

Hint

Use a Map to count characters in t and variables have and needCount to track matches.

3

Implement the sliding window logic in minWindow function

Create a function called minWindow that takes two strings s and t. Inside, use two pointers left and right to slide over s. Use a Map called window to count characters in the current window. Expand right pointer to include characters and update have when a needed character count matches. Then move left pointer to shrink the window while still containing all needed characters. Track the minimum window substring and return it at the end.

DSA Typescript

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

const need: Map = new Map();
for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
}
let have: number = 0;
const needCount: number = need.size;

// Create function minWindow(s: string, t: string): string
// Use sliding window with left and right pointers
// Use Map window to count characters in current window
// Update have when counts match need
// Shrink window from left while valid
// Track minimum window substring
// Return minimum window substring
// Your code here

Hint

Use two pointers and a Map to track characters in the window. Expand right pointer, then shrink left pointer while all needed characters are included.

4

Print the minimum window substring result

Print the result of calling minWindow(s, t).

DSA Typescript

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

const need: Map = new Map();
for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
}
let have: number = 0;
const needCount: number = need.size;

function minWindow(s: string, t: string): string {
    const window: Map = new Map();
    let left = 0;
    let right = 0;
    let res = "";
    let resLen = Infinity;
    let have = 0;

    for (right = 0; right < s.length; right++) {
        const c = s[right];
        window.set(c, (window.get(c) ?? 0) + 1);

        if (need.has(c) && window.get(c) === need.get(c)) {
            have++;
        }

        while (have === needCount) {
            if ((right - left + 1) < resLen) {
                res = s.substring(left, right + 1);
                resLen = right - left + 1;
            }

            const leftChar = s[left];
            window.set(leftChar, window.get(leftChar)! - 1);
            if (need.has(leftChar) && window.get(leftChar)! < need.get(leftChar)!) {
                have--;
            }
            left++;
        }
    }

    return resLen === Infinity ? "" : res;
}

// Print the result of minWindow(s, t)
// Your code here

Hint

Use console.log(minWindow(s, t)) to print the result.

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