Problem

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique. link

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10<sup>5</sup>
• s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution

Find a valid window, then shrink it to find the shortest one. A window is valid when it contains every required occurrence from t, including duplicates.

s = ADOBECODE[BANC]
t = ABC

BANC contains A, B, and C.
Shortest window length = 4

What the frequency array means

Initially, map[chr] stores how many occurrences of that character are required. As characters enter the window, decrement their values.

Value	Meaning
Positive	More occurrences are still needed
Zero	Exactly enough occurrences are present
Negative	Extra occurrences are present

count tracks matched occurrences, not distinct character types. For t = "AA", both occurrences must be matched before count == 2.

An array of size 128 supports direct indexing for the allowed English letters: A is 65 and z is 122. Uppercase and lowercase letters remain separate.

Brute force Approach

For every starting index i, build a fresh frequency array and extend the window to the right. After decrementing a value, increase count only if that value is nonnegative - the occurrence was needed.

When count == n, record the window if it is shorter and stop that inner loop. Extending the same window cannot produce a shorter answer.

Time: O(m × (m + n)) - rebuild the frequency array in O(n) for each start, plus up to O(m²) scanning.

class Solution {
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        int minLength = Integer.MAX_VALUE;
        int startIndex = m-1;

        for(int i=0; i<m; i++){
            int[] map = buildFrequency(t);
            int count = 0;
            for(int j=i; j<m; j++){
                char chr = s.charAt(j);
                map[chr] -= 1;

                if(map[chr] >= 0){
                    count +=1;
                }
                if(count == n){
                    if(minLength > j-i+1){
                        minLength = j-i+1;
                        startIndex = i;
                    }
                    break;
                }
            }

        }
        return minLength == Integer.MAX_VALUE? "" : s.substring(startIndex, startIndex+minLength);
    }

    private int[] buildFrequency(String t){
        int[] map = new int[128];

        for(Character chr : t.toCharArray()){
            map[chr]+=1;
        }
        return map;
    }
}

Optimal Approach

Build the frequency array once and reuse it with two pointers:

1. Expand: Add s[r], decrement its frequency, and count it if needed.
2. Record: While count == n, save the shortest window seen so far.
3. Shrink: Remove s[l] by incrementing its frequency. If the value becomes positive, a required occurrence is now missing, so decrease count.
4. Continue expanding when the window becomes invalid.

Record before removing the leftmost character, while the window is still valid. Extra occurrences can be removed without reducing count.

Time: O(m + n) - build the frequency array in O(n); each pointer moves forward at most m times.

class Solution {
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        int minLength = Integer.MAX_VALUE;
        int startIndex = m-1;

        
        int l= 0;
        int r = 0;

        int[] map = buildFrequency(t);
        int count = 0;

        while(r<m){

            int index = s.charAt(r);

            map[index] -= 1;

            if(map[index] >= 0) {
                count+=1;
            }

            while(count == n){
                if(minLength > r-l+1){
                    minLength = r-l+1;
                    startIndex = l;
                }

                char chr = s.charAt(l);

                map[chr] += 1;
                
                if(map[chr] > 0) count-=1;

                l+=1;
            }

            r+=1;
        }

        return minLength == Integer.MAX_VALUE? "" : s.substring(startIndex, startIndex+minLength);
    }

    private int[] buildFrequency(String t){
        int[] map = new int[128];

        for(Character chr : t.toCharArray()){
            map[chr]+=1;
        }
        return map;
    }
}

Space used by these implementations

The 128-element frequency array uses O(1) space. The helper also calls t.toCharArray(), which creates a temporary array of length n, so both implementations use O(n) auxiliary space, excluding the returned substring.