How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Lyft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Lyft during technical interviews.

Smallest Covering Window in a String

Quick Overview

This question evaluates a candidate's ability to apply the sliding window technique to substring search problems. It tests understanding of two-pointer window expansion and contraction, character frequency tracking, and edge-case handling, commonly asked to assess practical coding proficiency in string and array manipulation.

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

# Smallest Covering Window in a String You are given two strings, `source` and `target`. Return the **shortest contiguous substring** of `source` that contains **every character of `target`, including repeated characters**. That is, if `target` contains a character `c` exactly `k` times, the substring you return must contain `c` at least `k` times. If no such substring exists, return an empty string `""`. Note: the interviewer does not provide test cases. You are expected to construct your own inputs (including edge cases such as no valid window, an exact full-string match, and characters that must appear multiple times) and validate your solution against them. ### Input - `source`: a string of length `m`. - `target`: a string of length `n`. - Both strings consist of uppercase and lowercase English letters (`a`–`z`, `A`–`Z`). Matching is **case-sensitive**, so `'a'` and `'A'` are treated as different characters. ### Output - The shortest substring of `source` that covers all characters of `target` (counting multiplicity). - If multiple shortest substrings exist, return the one that starts at the smallest index. - If no valid substring exists, return `""`. ### Constraints - `1 <= m, n <= 10^5` - A target runtime of `O(m + n)` is expected (a single forward pass with two pointers / a sliding window). Pay particular attention to **when** each pointer should advance and **when** the window may shrink while remaining valid. ### Examples **Example 1** - `source = "ADOBECODEBANC"`, `target = "ABC"` - Output: `"BANC"` - Explanation: `"BANC"` is the shortest window that contains one `'A'`, one `'B'`, and one `'C'`. **Example 2** - `source = "a"`, `target = "a"` - Output: `"a"` **Example 3** - `source = "a"`, `target = "aa"` - Output: `""` - Explanation: `'a'` occurs only once in `source`, so it can never cover two `'a'`s. **Example 4 (multiplicity matters)** - `source = "aab"`, `target = "ab"` - Output: `"ab"` - Explanation: A single `'a'` plus the `'b'` is enough; the second `'a'` is not required. **Example 5 (tie-break on start index)** - `source = "abba"`, `target = "ab"` - Output: `"ab"` - Explanation: Both `"ab"` (starting at index 0) and `"ba"` (starting at index 2) have length 2; return the one with the smaller start index.

Quick Answer: This question evaluates a candidate's ability to apply the sliding window technique to substring search problems. It tests understanding of two-pointer window expansion and contraction, character frequency tracking, and edge-case handling, commonly asked to assess practical coding proficiency in string and array manipulation.

You are given two strings, `source` and `target`. Return the **shortest contiguous substring** of `source` that contains **every character of `target`, including repeated characters**. That is, if `target` contains a character `c` exactly `k` times, the substring you return must contain `c` at least `k` times. If no such substring exists, return an empty string `""`. ### Input - `source`: a string of length `m`. - `target`: a string of length `n`. - Both strings consist of uppercase and lowercase English letters (`a`-`z`, `A`-`Z`). Matching is **case-sensitive**, so `'a'` and `'A'` are treated as different characters. ### Output - The shortest substring of `source` that covers all characters of `target` (counting multiplicity). - If multiple shortest substrings exist, return the one that starts at the smallest index. - If no valid substring exists, return `""`. ### Constraints - `1 <= m, n <= 10^5` - Target runtime `O(m + n)` (single forward pass with a two-pointer sliding window). ### Examples - `source = "ADOBECODEBANC"`, `target = "ABC"` -> `"BANC"` - `source = "a"`, `target = "a"` -> `"a"` - `source = "a"`, `target = "aa"` -> `""` - `source = "aab"`, `target = "ab"` -> `"ab"` - `source = "abba"`, `target = "ab"` -> `"ab"` (tie-break on smaller start index)

Constraints

1 <= m, n <= 10^5
source and target consist only of uppercase and lowercase English letters
Matching is case-sensitive ('a' != 'A')
Repeated characters in target must be covered with their full multiplicity

Examples

Input: ("ADOBECODEBANC", "ABC")

Expected Output: "BANC"

Explanation: "BANC" is the shortest window containing one A, one B, and one C.

Input: ("a", "a")

Expected Output: "a"

Explanation: The entire single-character string is the window.

Input: ("a", "aa")

Expected Output: ""

Explanation: source has only one 'a', so it can never cover two 'a's.

Input: ("aab", "ab")

Expected Output: "ab"

Explanation: One 'a' plus 'b' suffices; the second 'a' is not required.

Input: ("abba", "ab")

Expected Output: "ab"

Explanation: Both "ab" (index 0) and "ba" (index 2) have length 2; return the smaller start index.

Input: ("xyz", "a")

Expected Output: ""

Explanation: 'a' never appears in source, so no valid window exists.

Input: ("aa", "aa")

Expected Output: "aa"

Explanation: Multiplicity: two 'a's are needed and the whole string provides exactly two.

Input: ("cabwefgewcwaefgcf", "cae")

Expected Output: "cwae"

Explanation: "cwae" is the shortest window covering c, a, and e.

Hints

Use a sliding window with two pointers. Expand the right pointer to include characters, and shrink the left pointer once the window is valid.
Keep a count of how many required characters are still 'missing'. A window is valid exactly when missing == 0.
Only decrement missing when the character you add was actually still needed (its need count was > 0 before adding). Symmetrically, only increment missing when removing a character drops its need count above 0.
Because you record the best window while shrinking (using strict '<' on length), the first-found smallest window naturally has the smallest start index.

Quick Overview