# Minimum Window Substring

# 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](https://leetcode.com/problems/minimum-window-substring/description/)

**Example 1:**

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

**Example 2:**

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

**Example 3:**

```plaintext
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.

```text
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.

```java
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.

```java
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.