LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

LinkedIn SWE coding round, one algorithmic problem the whole time. 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 shortest substring of s that contains every character from t, including duplicates. Return an empty string if none exists.

Algorithms & Data Structures

Author's notes

The O(n) constraint is what makes this non-trivial.

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 from t. Maintain a 'formed' counter to know when the window contains all required characters, and record the minimum length window. Return the smallest valid window or empty string if none exists.

Pro tip: Clarify edge cases upfront (e.g., t longer than s, empty strings) and discuss trade-offs between the sliding window O(n) approach and a brute-force O(n^2) method to show depth. Mention that the window is always valid when formed == required, and you only shrink when it remains valid.

1. Clarify requirements and edge cases

Confirm that t may have duplicates, s and t can be empty, and return empty string if no valid substring. Ask if characters are case-sensitive or limited to ASCII.

2. Choose sliding window approach

Explain that a brute-force check of all substrings is O(n^2) or worse, while a sliding window with hash maps achieves O(n) time and O(k) space, where k is the number of unique characters in t.

3. Initialize data structures

Create a frequency map for t (dict_t) and a window frequency map (window_counts). Track 'formed' (number of characters meeting required frequency) and 'required' (unique characters in t).

4. Expand and contract window

Move right pointer to include characters, updating window_counts and formed. When formed == required, shrink from left while maintaining validity, updating the minimum window length and start index.

5. Return result and analyze complexity

After traversal, return the substring using the recorded start and min length, or empty string if none found. State time complexity O(|s| + |t|) and space O(|s| + |t|) or O(k).

Key Points to Mention

Sliding window technique with two pointers (left and right) to avoid redundant checks.
Use of hash maps (or arrays for fixed character set) to track character frequencies in t and the current window.
The 'formed' counter to efficiently check when the window contains all required characters with correct counts.
Shrinking the window only when it remains valid to find the minimum length.
Handling edge cases: empty strings, t longer than s, no valid substring.
Time and space complexity analysis: O(n) time, O(k) space where k is unique characters in t.

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