> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/minimum-window-substring.md).

# 76. Minimum Window Substring

### Description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

**Note:**

* If there is no such window in S that covers all characters in T, return the empty string `""`.
* If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/find-the-smallest-window-in-a-string-containing-all-characters-of-another-string/)
* [Leetcode](https://leetcode.com/problems/minimum-window-substring/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-minimum-window-substring-java/)
* [YouTube](https://youtu.be/eS6PZLjoaq8)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** S = "ADOBECODEBANC", T = "ABC"

**Output:** "BANC"
{% endtab %}

{% tab title="Example 2" %}
**Input:** S = "ADOBECODEBANC", T = "ABCZ"

**Output:** ""
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || t == null || s.isEmpty()) return "";
        
        int sLen = s.length(), tLen = t.length();
        int[] sHash = new int[128];
        int[] tHash = new int[128];
        
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        for(char ch: tChars) {
            tHash[ch]++;
        }
        
        int left = 0, start = -1, count = 0, minLen = Integer.MAX_VALUE;
        for(int right = 0; right < sLen; right++) {
            char ch = sChars[right];
            
            sHash[ch]++;
            if(tHash[ch] != 0 && sHash[ch] <= tHash[ch]) count++;
            
            if(count == tLen) {
                while(tHash[sChars[left]] == 0 || 
                     sHash[sChars[left]] > tHash[sChars[left]]) {
                    
                    if(sHash[sChars[left]] > tHash[sChars[left]]) {
                        sHash[sChars[left]]--;
                    }
                    left++;
                }
                if(minLen > right-left+1) {
                    minLen = right-left+1;
                    start = left;
                }
            }
        }
        
        return (start == -1)? "": s.substring(start, start+minLen);
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Minimum length substring with exactly K distinct characters - [GFG](https://www.geeksforgeeks.org/minimum-length-substring-with-exactly-k-distinct-characters/)
* Program to find the largest and smallest ASCII valued characters in a string - [GFG](https://www.geeksforgeeks.org/program-to-find-the-largest-and-smallest-ascii-valued-characters-in-a-string/)