Smallest Window Containing All Characters of Another String

Hard30–35 min

Topics

StringSliding WindowHash Table

Companies

AmazonMicrosoftGoogleFacebookUber

Given two strings s and t, return the shortest contiguous substring of s that contains every character of t (including repeats — if t has two 'a's, the window needs at least two). If no such window exists, return an empty string. Unlike a fixed-size window, this window's size isn't known in advance — it has to grow and shrink as the scan progresses. The sliding window technique tracks a frequency count of the window's characters alongside a formed counter — how many of t's distinct characters are currently satisfied. Grow the window right until formed reaches the required count, then greedily shrink from the left — recording the shortest valid window at every step — until a character falls short again. Every character is visited once by each pointer, so the whole scan runs in O(n).

Test Case 1:

Input:s = "aabec", t = "abc"

Output:"abec"

Explanation:The window "abec" (indices 1-4) is the shortest window of s that contains every character of t.

Test Case 2:

Input:s = "adobecodebanc", t = "abc"

Output:"banc"

Explanation:The window "banc" is the shortest window that contains an 'a', a 'b', and a 'c'.

Test Case 3:

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

Output:"a"

Explanation:The whole string is already the answer.

Constraints

◆1 ≤ s.length, t.length ≤ 10⁵
◆s and t consist of lowercase English letters only
◆t.length ≤ s.length

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (lowercase) — 3-10 lowercase letterst (lowercase) — 1-5 lowercase letters, at most as long as s

1	class Solution {
2	public String smallestWindowContainingAllChars(String s, String t) {
3	int n = s.length();
4	int[] need = new int[26];
5	int required = 0;
6	for (char c : t.toCharArray()) {
7	if (need[c - 'a'] == 0) required++;
8	need[c - 'a']++;
9	}
10	int[] window = new int[26];
11	int left = 0, formed = 0, bestLen = n + 1, bestStart = -1;
12	for (int right = 0; right < n; right++) {
13	int idx = s.charAt(right) - 'a';
14	window[idx]++;
15	if (need[idx] > 0 && window[idx] == need[idx]) formed++;
16	while (formed == required) {
17	if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
18	int leftIdx = s.charAt(left) - 'a';
19	window[leftIdx]--;
20	if (need[leftIdx] > 0 && window[leftIdx] < need[leftIdx]) formed--;
21	left++;
22	}
23	}
24	return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
25	}
26	}
27

Variables

left0

formed0

bestLenn + 1

bestStart-1

INITIALIZE

Start left and formed at 0, and bestStart at -1 (no window found yet). The window's own frequency count starts empty.

Step 1 / 11

Approach & Solutions

Brute Force

Brute

Build a 26-letter frequency count for t, and count how many distinct characters it requires. For every possible starting index, grow the window to the right — tracking a frequency count of its own — stopping the moment every required character's count is satisfied, then record that window's length. Correct, but every start re-scans and rebuilds its own count from scratch, throwing away everything the previous start already discovered.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public String smallestWindowContainingAllChars(String s, String t) {
        int n = s.length();
        int[] need = new int[26];
        int required = 0;
        for (char c : t.toCharArray()) {
            if (need[c - 'a'] == 0) required++;
            need[c - 'a']++;
        }
        int bestLen = n + 1, bestStart = -1;
        for (int i = 0; i < n; i++) {
            int[] count = new int[26];
            int formed = 0;
            for (int j = i; j < n; j++) {
                int idx = s.charAt(j) - 'a';
                count[idx]++;
                if (need[idx] > 0 && count[idx] == need[idx]) formed++;
                if (formed == required) {
                    if (j - i + 1 < bestLen) { bestLen = j - i + 1; bestStart = i; }
                    break;
                }
            }
        }
        return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}

Optimal — Sliding Window

Optimal

Build t's 26-letter frequency count once, plus how many distinct characters it requires. Grow a window to the right, tracking its own frequency count and how many of the required characters are currently satisfied. The moment all of them are satisfied, shrink from the left one character at a time — recording the best (shortest) window before every shrink — until a required character falls short again. Every character is visited once by the right pointer and at most once by the left pointer, so the whole scan runs in O(n).

TimeO(n)