Skip to content

Smallest Covering Snippet

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Smallest Covering Snippet

A search tool has a document s and a set of required characters t (duplicates in t count). It wants the shortest contiguous window of s that contains every character of t, including repeats.

Return that minimum window substring, or "" if none exists.

def min_window(s, t):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Strings, Sliding Window, Hashmaps

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: Do duplicate characters in t need to appear multiple times in the window?
    • A: Yes. If t = "aa", the window must contain at least two 'a' characters. One 'a' is not enough.
  • Q: Does the window need the characters of t in any particular order, or must the window contain only those characters?
    • A: No. The window is any contiguous substring of s that contains all characters of t in any order, and it may include extra characters that are not in t.
  • Q: What should be returned if no window of s covers all of t?
    • A: Return the empty string "".
HAPPY CASE
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the shortest substring of s that contains 'A', 'B', and 'C'.

EDGE CASE
Input: s = "a", t = "aa"
Output: ""
Explanation: t requires two 'a' characters but s only has one, so no valid window exists.

Input: s = "aa", t = "aa"
Output: "aa"
Explanation: The entire document is the smallest window that covers both required 'a' characters.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Substring Search Problems, we can consider the following approaches:

  • Sliding Window (two pointers): Grow a window on the right until it covers all of t, then shrink it from the left while it stays valid. This finds the minimum covering window in one pass.
  • Hashmap (frequency counting): Track how many of each required character the current window still needs, so validity can be checked in O(1) per step instead of rescanning the window.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Keep a hashmap need of how many of each character the window still requires, plus a counter missing of the total characters still missing. Sweep a right pointer across s, absorbing characters into the window. Whenever missing reaches 0, the window covers t, so advance the left pointer past any surplus characters and record the window if it is the smallest seen so far.

1) If s or t is empty, or t is longer than s, return "".
2) Build a hashmap `need` counting each character of t, and set `missing = len(t)`.
3) Initialize left = 0 and an empty best window.
4) For each right index, absorb character s[right] into the window:
   a) If need[s[right]] > 0, this character was still required, so decrement missing.
   b) Decrement need[s[right]] (counts below zero mean surplus copies in the window).
5) While missing == 0 (the window covers all of t):
   a) Shrink from the left while s[left] is surplus (need[s[left]] < 0), restoring counts as it exits.
   b) If the current window is shorter than the best so far, record it.
6) Return the best window found, or "" if none was ever recorded.

⚠️ Common Mistakes

  • Checking window validity by rescanning the whole window each time, turning an O(N) sweep into O(N^2) or worse.
  • Ignoring duplicates in t — a window with one 'a' is not valid when t = "aa".
  • Forgetting to restore need counts (and missing when appropriate) as characters leave the window on the left.
  • Returning the first valid window found instead of continuing to shrink and slide for a smaller one.

4: I-mplement

Implement the code to solve the algorithm.

def min_window(s, t):
    if not s or not t or len(t) > len(s):
        return ""

    # Count how many of each required character we still need
    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1
    missing = len(t)  # Total characters still missing from the window

    left = 0
    best_start, best_end = 0, 0  # Best window found so far (best_end == 0 means none)

    for right, char in enumerate(s, 1):  # right is 1 past the current character
        # Expand the window: absorb s[right - 1]
        if need.get(char, 0) > 0:
            missing -= 1
        need[char] = need.get(char, 0) - 1

        # When the window covers all of t, shrink from the left
        if missing == 0:
            while need[s[left]] < 0:  # s[left] is surplus; drop it
                need[s[left]] += 1
                left += 1
            # Record the window if it is the smallest so far
            if best_end == 0 or right - left < best_end - best_start:
                best_start, best_end = left, right

    return s[best_start:best_end]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: s = "ADOBECODEBANC", t = "ABC"

    • The window expands to "ADOBEC" (indices 0-5), the first window covering 'A', 'B', and 'C'; nothing on the left is surplus, so it is recorded (length 6).
    • Expanding further to "ADOBECODEBA" lets the left side shrink past "ADOBEC" to "CODEBA" (length 6, not smaller).
    • When the final 'C' arrives, the window shrinks to "BANC" (length 4), which is recorded as the new best.
    • Output: "BANC"

  • Input: s = "a", t = "aa"

    • missing starts at 2. The single 'a' drops it to 1, but it never reaches 0, so no window is recorded.
    • Output: ""

  • Input: s = "aa", t = "aa"

    • After the second 'a', missing reaches 0 with the window spanning the whole string, and no left character is surplus.
    • Output: "aa"

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the document s, M is the length of the required characters t, and K is the number of distinct characters in s and t.

  • Time Complexity: O(N + M) because building need takes O(M), and each character of s is visited at most twice — once when the right pointer absorbs it and once when the left pointer releases it.
  • Space Complexity: O(K) for the need hashmap, which holds one counter per distinct character.

Clone this wiki locally