Minimum Window Substring in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Window Substring Function

What is the output of the following TypeScript function call?

Function finds the smallest substring in s containing all characters of t.

DSA Typescript

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

console.log(minWindow("ADOBECODEBANC", "ABC"));

A "ADOBEC"

B "CODEBA"

C "BANC"

D "DOBECODEBA"

💡 Hint

Focus on the smallest substring that contains all characters A, B, and C.

The smallest substring of "ADOBECODEBANC" containing all characters 'A', 'B', and 'C' is "BANC".

🧠 Conceptual

intermediate

Minimum Window Substring Sliding Window Concept

In the sliding window approach for Minimum Window Substring, what does the variable count typically represent?

A The index of the start of the minimum window found so far

B The length of the current window

C The total number of unique characters in the source string

D The number of characters still needed to complete the substring containing all target characters

💡 Hint

Think about what needs to be tracked to know when the window contains all required characters.

The variable count tracks how many characters from the target string are still needed in the current window to satisfy the condition.

🔧 Debug

advanced

Identify the Error in Minimum Window Substring Code

What error will the following TypeScript code produce when executed?

DSA Typescript

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

minWindow("a", "a");

A TypeError: Cannot read property 'valueOf' of undefined

B No error, returns "a"

C SyntaxError: Unexpected token

D ReferenceError: need is not defined

💡 Hint

Check how Map.get() is used without null checks.

The code calls need.get(c) without the non-null assertion operator, so TypeScript infers possible undefined, causing runtime TypeError when subtracting from undefined.

❓ Predict Output

advanced

Result of Minimum Window Substring with Repeated Characters

What is the output of the following code?

DSA Typescript

console.log(minWindow("aabbccdd", "abc"));

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

A "abc"

B "abbc"

C "bca"

D "aabbc"

💡 Hint

Look for the smallest substring containing at least one 'a', one 'b', and one 'c'.

The substring "abbc" is the smallest window containing all characters 'a', 'b', and 'c'.

🧠 Conceptual

expert

Time Complexity of Minimum Window Substring Algorithm

What is the time complexity of the optimal sliding window algorithm for the Minimum Window Substring problem, where n is the length of the source string and m is the length of the target string?

A O(n + m)

B O(n * m)

C O(n^2)

D O(m^2)

💡 Hint

Consider how many times each pointer moves in the sliding window approach.

Each character in the source string is visited at most twice (once when expanding right pointer, once when moving left pointer), and building the frequency map takes O(m). So total is O(n + m).

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