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

Intermediate

Jun 2026

Summary

Google SWE coding round, one question on substring search. Pretty standard sliding window territory but the details matter more than you'd think.

Questions Asked (1)

Given two strings s and t, find the smallest substring of s that contains all characters of t, including duplicates. Return an empty string if none exists. Walk through your approach.

Algorithms & Data Structures

Author's notes

The sliding window with a frequency counter is the move here.

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 maintaining a frequency map of characters in t. Track the minimum window that contains all required characters, and return it or an empty string if none exists.

Pro tip: Clarify edge cases upfront (e.g., t longer than s, empty strings) and mention that the algorithm runs in O(n + m) time using a hash map or fixed-size array for character counts.

1. Clarify requirements and edge cases

Confirm that duplicates in t must be matched, and discuss cases like empty strings, t longer than s, or characters not in s.

2. Choose data structures

Use a frequency map (or array of size 128/256) to count characters in t, and a counter to track how many required characters are currently satisfied in the window.

3. Expand the window

Move the right pointer to include characters from s, updating the frequency map and the satisfied counter until all characters of t are covered.

4. Contract the window

While the window is valid, move the left pointer to shrink the window, updating the minimum length and start index, and adjusting the frequency map and satisfied counter.

5. Return the result

After scanning s, return the smallest substring found, or an empty string if no valid window exists.

Key Points to Mention

Sliding window technique with two pointers (left and right).
Frequency map or array to track character counts, handling duplicates.
A 'formed' or 'satisfied' counter to efficiently check if the window contains all characters of t.
Time complexity O(n + m) and space complexity O(k) where k is the character set size.
Edge cases: empty strings, t longer than s, no valid substring.
Optimization: using an array instead of a hash map for ASCII characters.

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