Minimum Window Substring in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Window Substring Function

What is the output of the following Python code that finds the minimum window substring containing all characters of t in s?

DSA Python

def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    for right, char in enumerate(s, 1):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[start:end]

print(min_window("ADOBECODEBANC", "ABC"))

A "BANC"

B "ADOBEC"

C "CODEBA"

D "DOBECODEBA"

💡 Hint

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

The function finds the smallest substring in s that contains all characters of t. The substring "BANC" is the shortest that contains A, B, and C.

❓ Predict Output

intermediate

Minimum Window Substring with Repeated Characters

What is the output of this code when s contains repeated characters and t requires multiple occurrences?

DSA Python

def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    for right, char in enumerate(s, 1):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[start:end]

print(min_window("AAABBC", "AABC"))

A "AABB"

B "AAABBC"

C "AABBC"

D "ABBC"

💡 Hint

Remember t requires two 'A's, one 'B', and one 'C'.

The minimum window substring containing two 'A's, one 'B', and one 'C' is "AABBC".

🔧 Debug

advanced

Identify the Error in Minimum Window Substring Code

What error will this code raise when executed?

DSA Python

def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[start:end]

print(min_window("ADOBECODEBANC", "ABC"))

A Returns empty string

B TypeError

C IndexError

D Returns incorrect substring "BANC"

💡 Hint

Check how the right pointer is used in slicing the string.

The code uses zero-based indexing for right but slices s[start:end] where end is zero-based, missing the last character. Also, right is zero-based but the loop does not add 1, so the substring is empty.

🧠 Conceptual

advanced

Why Use a Sliding Window in Minimum Window Substring?

Why is the sliding window technique suitable for solving the Minimum Window Substring problem?

A Because it sorts the string to find the substring faster

B Because it allows checking all substrings by expanding and contracting the window efficiently

C Because it uses recursion to explore all substring possibilities

D Because it converts the string into a graph for traversal

💡 Hint

Think about how to find the smallest substring containing all needed characters without checking every substring.

Sliding window expands to include needed characters and contracts to remove unnecessary ones, efficiently finding the minimum substring.

🚀 Application

expert

Minimum Window Substring with Unicode Characters

Given the string s = "𝔸𝔹𝔸𝔻𝔸𝔹𝔠" and t = "𝔸𝔠", what is the minimum window substring containing all characters of t?

A "𝔸𝔹𝔸𝔻𝔸𝔹𝔠"

B "𝔠"

C "𝔹𝔠"

D "𝔸𝔹𝔠"

💡 Hint

Unicode characters count as single characters; find the shortest substring containing both.

The substring "𝔸𝔹𝔠" is the shortest substring containing both "𝔸" and "𝔠" in the given string.