Minimum Window Substring in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Window Substring Function

What is the output of the following JavaScript function call?

DSA Javascript

function minWindow(s, t) {
  if (t.length > s.length) return "";
  const need = new Map();
  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 "BANC"

B "DOBECODEBA"

C "CODEBA"

D "ADOBEC"

💡 Hint

Think about the smallest substring that contains all characters from t.

The minimum window substring containing all characters 'A', 'B', and 'C' in "ADOBECODEBANC" is "BANC".

❓ Predict Output

intermediate

Result of Minimum Window Substring with Repeated Characters

What will the function return for this input?

DSA Javascript

function minWindow(s, t) {
  if (t.length > s.length) return "";
  const need = new Map();
  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("AAABBC", "ABC"));

A "AB"

B "AABBC"

C "AAABBC"

D "ABBC"

💡 Hint

Look for the smallest substring containing one 'A', one 'B', and one 'C'.

The smallest substring containing 'A', 'B', and 'C' is "ABBC" starting at index 2.

🔧 Debug

advanced

Identify the Error in Minimum Window Substring Implementation

What error will this code produce when run?

DSA Javascript

function minWindow(s, t) {
  const need = new Map();
  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(null, "ABC"));

A TypeError: Cannot read property 'length' of null

B ReferenceError: s is not defined

C SyntaxError: Unexpected token

D Returns empty string ""

💡 Hint

Check what happens when s is null and length is accessed.

The code tries to access s.length but s is null, causing a TypeError.

🧠 Conceptual

advanced

Minimum Window Substring Algorithm Complexity

What is the time complexity of the standard sliding window algorithm for Minimum Window Substring?

A O(n log n) due to sorting inside the window

B O(n) because each character is visited at most twice

C O(n^2) because of nested loops

D O(1) constant time because of fixed window size

💡 Hint

Consider how many times the left and right pointers move.

Each character is visited at most twice by left and right pointers, so time complexity is O(n).

🚀 Application

expert

Find Minimum Window Substring Containing All Unique Characters

Given the string s = "aabcbcdbca", what is the minimum window substring that contains all unique characters of s?

A "bcbcdbca"

B "cbcdbca"

C "dbca"

D "abcbcdbca"

💡 Hint

First find all unique characters, then find the smallest substring containing them all.

All unique characters are {a,b,c,d}. The smallest substring containing all is "dbca".

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