Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Meta SWE coding round, one question the whole time: minimum window substring. Classic sliding window problem but I kept second-guessing my pointer logic under pressure.

Questions Asked (1)

Given two strings s and t, find the shortest contiguous substring of s that contains all characters of t (with duplicates counted). Return an empty string if no such substring exists.

Algorithms & Data Structures

Author's notes

I knew it was a sliding window problem pretty fast, two pointers, frequency map, shrink from the left when you have a valid window.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a sliding window with two pointers to expand and contract a window over s while tracking character counts of t. Maintain a 'formed' counter to know when the window contains all required characters, and record the minimum length window. Return the shortest substring found or empty string if none exists.

Pro tip: Clarify edge cases upfront (e.g., t longer than s, empty strings) and state the time complexity O(|s| + |t|) and space O(|s| + |t|) to show thoroughness. Also, mention that you'd test with duplicate characters in t to ensure correctness.

1. Understand the problem and edge cases

Restate the problem to confirm understanding: find the shortest contiguous substring of s containing all characters of t with duplicates. Discuss edge cases like empty strings, t longer than s, or no valid substring.

2. Choose the sliding window approach

Explain that a brute-force check of all substrings is O(n^2) and inefficient. Propose a sliding window (two pointers) technique to achieve O(n) time by expanding and contracting the window.

3. Define data structures and counters

Use a frequency map for characters in t and a dynamic count for the current window. Maintain a 'formed' counter to track how many characters have met the required frequency, and variables for min length and start index.

4. Implement the sliding window logic

Expand the right pointer to include characters, updating counts and 'formed'. When 'formed' equals the number of unique characters in t, contract the left pointer to minimize the window while updating the minimum length and start index.

5. Return the result and analyze complexity

After traversal, return the substring using the recorded start and min length, or empty string if no valid window. State time complexity O(|s| + |t|) and space O(|s| + |t|) for the frequency maps.

Key Points to Mention

Sliding window technique with two pointers (left and right) to avoid O(n^2) brute force.
Frequency maps (hash maps or arrays) to count characters in t and the current window.
'Formed' counter to track how many unique characters in t have been fully matched in the window.
Contracting the window when all characters are matched to find the minimum length.
Handling duplicates in t by comparing exact frequencies.
Time and space complexity analysis: O(|s| + |t|) time and O(|s| + |t|) space.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.