Data Structures & Algorithms (Sliding Window): Minimum Window Substring

February 9, 2026

Given two strings s and t, return the smallest substring of s that contains all the characters in t (including duplicates). If no such string exists, return an empty string "".

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "aaaabbbbbcdd", t = "abcdd"
Output: "abbbbbcdd"

Playground: Leetcode 76

General Observations

Below are a few key insights that will help us figure out a suitable algorithm to solve this problem:

Q1. How to check if a substring of s is a valid candidate?

We can maintain a frequency map of t. If a substring of s contains every character from t with at least its required frequency, then the substring is a valid candidate.

Q2. Can there be multiple correct answers?

No, we can assume all test cases will have a unique answer.

Brute Force Approach - Nested Loops

Loop over each substring of s and keep track of the smallest substring that contains all the required characters from t with at least the required frequencies.

Algorithm

1. Create a frequency map of all characters in "t".
2. Initialize variables to store the length and value of the smallest valid substring found so far.

3. Start from every character in "s" and expand the substring one character at a time.
4. Maintain a frequency map for the required characters present in the current substring.
5. After each expansion, check whether the current substring contains every character from "t" 
   with at least the required frequency.
6. If it is valid and shorter than the current minimum, update the answer.

7. After checking all possible substrings, return the smallest valid substring.

Implementation

Sample inputs
1public String minWindow(String s, String t) {
2 // 1. Build the frequency map of required characters from t
3 Map<Character, Integer> reqFreqMap = new HashMap<>();
4 for (char ch : t.toCharArray()) {
5 reqFreqMap.put(ch, reqFreqMap.getOrDefault(ch, 0) + 1);
6 }
7
8 // 2. Initialize the smallest valid substring
9 int minLength = Integer.MAX_VALUE;
10 String smallestSubstring = "";
11
12 // 3. Consider every possible starting index
13 for (int start = 0; start < s.length(); start++) {
14 Map<Character, Integer> currFreqMap = new HashMap<>();
15
16 // 4. Expand the substring from start
17 for (int end = start; end < s.length(); end++) {
18 char ch = s.charAt(end);
19 // Track only characters present in t
20 if (reqFreqMap.containsKey(ch)) {
21 currFreqMap.put(ch, currFreqMap.getOrDefault(ch, 0) + 1);
22 }
23
24 // 5. Check if the current substring is valid
25 boolean valid = true;
26 for (char reqChar : reqFreqMap.keySet()) {
27 int reqFreq = reqFreqMap.get(reqChar);
28 int currFreq = currFreqMap.getOrDefault(reqChar, 0);
29 if (currFreq < reqFreq) {
30 valid = false;
31 break;
32 }
33 }
34
35 // 6. Update the smallest valid substring
36 int currLength = end - start + 1;
37 if (valid && currLength < minLength) {
38 minLength = currLength;
39 smallestSubstring = s.substring(start, end + 1);
40 }
41 }
42 }
43
44 // 7. Return the smallest valid substring
45 return smallestSubstring;
46}
t
A
B
C
Input string s
end
end
end
end
A
B
A
C
start
start
start
start
0
1
2
3
Current window—
s[start..end]len —
reqFreqMap vs currFreqMap
Empty — still building reqFreqMap
start= —
end= —
minLength= ∞
smallestSubstring
""
Ready
Press Play or Step to dry-run the nested loops. Highlighted lines are the ones currently executing.
0/29

Time Complexity

There are n(n+1)/2 possible substrings of s, so traversing all substrings contributes O(n²).

For each substring, we iterate over reqFreqMap to check whether every required character is present with the required frequency. This takes O(k), where k is the number of distinct characters in t.

Hence, the overall time complexity will be O(n² · k).

Space Complexity

Both reqFreqMap and currFreqMap will store the frequency of all the distinct characters in t. Assuming k is the number of distinct characters in t, the overall space complexity will be O(k).

Key Optimization

Once the current window [start, end] becomes valid, it contains all the characters present in t. We can make a few observations to avoid performing unncessary work from the brute-force (nested-loop) approach:

  1. No need to explore earlier ending positions: Since the previous window [start, end-1] was invalid, any smaller window ending at or before end-1 will also be invalid because it contains even fewer characters. Therefore, there is no need to explore those windows again.

invalid-substrings

  1. Shrink the current valid window: The current window may contain unnecessary characters at the beginning. Therefore, we can increment start to remove characters from the left and try to find a smaller valid window ending at end.

valid-substrings

Sliding Window Approach

Use two pointers: [start, end] to maintain a sliding window containing the current substring. Move end forward until the window becomes valid, then move start forward to make the valid window as small as possible.

Algorithm

1. Create a frequency map of all characters in "t".
2. Initialize variables to store the length and value of the smallest valid substring found so far.

3. Initialize two pointers, "start" and "end", to represent the boundaries of the current sliding window.
4. Increment "end" to expand the window one character at a time and update the frequency of the 
   required characters in the current window.
5. For each expansion, check if the current window contains every character from "t" with at least
   the required frequency.
6. While the current window is valid:
      - Update the smallest valid substring is the current window is smaller.
      - Increment "start" to shrink the window.
      - If character removed from the window is required by "t", update its frequency in the current window.

7. Return the shortest valid substring.

Implementation

Sample inputs
1class Solution {
2
3 private boolean isValid(
4 Map<Character, Integer> reqFreqMap,
5 Map<Character, Integer> currFreqMap) {
6
7 for (char reqChar : reqFreqMap.keySet()) {
8 int reqFreq = reqFreqMap.get(reqChar);
9 int currFreq = currFreqMap.getOrDefault(reqChar, 0);
10
11 if (currFreq < reqFreq) {
12 return false;
13 }
14 }
15
16 return true;
17 }
18
19 public String minWindow(String s, String t) {
20
21 // 1. Frequency map of every character in t.
22 Map<Character, Integer> reqFreqMap = new HashMap<>();
23
24 for (char ch : t.toCharArray()) {
25 reqFreqMap.put(ch, reqFreqMap.getOrDefault(ch, 0) + 1);
26 }
27
28 // 2. Smallest valid substring found so far.
29 int minLength = Integer.MAX_VALUE;
30 String smallestSubstring = "";
31
32 // 3. Window is the substring s[start..end].
33 int start = 0;
34 int end = 0;
35 Map<Character, Integer> currFreqMap = new HashMap<>();
36
37 // 4. Expand the window with end.
38 while (end < s.length()) {
39
40 char endChar = s.charAt(end);
41
42 if (reqFreqMap.containsKey(endChar)) {
43 currFreqMap.put(
44 endChar,
45 currFreqMap.getOrDefault(endChar, 0) + 1
46 );
47 }
48
49 // 5-6. While the window is valid, shrink from the left.
50 while (start <= end && isValid(reqFreqMap, currFreqMap)) {
51
52 int currLength = end - start + 1;
53
54 if (currLength < minLength) {
55 minLength = currLength;
56 smallestSubstring = s.substring(start, end + 1);
57 }
58
59 char startChar = s.charAt(start);
60
61 if (reqFreqMap.containsKey(startChar)) {
62 int currFreq = currFreqMap.get(startChar);
63 if (currFreq == 1) {
64 currFreqMap.remove(startChar);
65 } else {
66 currFreqMap.put(startChar, currFreq - 1);
67 }
68 }
69
70 start++;
71 }
72
73 end++;
74 }
75
76 // 7. Return the smallest valid substring.
77 return smallestSubstring;
78 }
79}
t
A
B
C
Input string s
end
end
end
end
A
B
A
C
start
start
start
start
0
1
2
3
Current window—
s[start..end]len —
reqFreqMap vs currFreqMap
Empty — still building reqFreqMap
start= —
end= —
minLength= ∞
smallestSubstring
""
Ready
Press Play or Step. Highlighted lines are the ones executing, and the window on the right updates with them.
0/24

Time Complexity

Each character in s is processed at most twice: once when the end pointer expands the window and once when the start pointer shrinks the window.

For each validity check, we iterate over all distinct characters in t, which takes O(k), where k is the number of distinct characters in t.

Therefore, the overall time complexity is O(n · k).

Space Complexity

The overall auxiliary space complexity is the same as the brute-force approach, i.e., O(k), where k is the number of distinct characters in t.