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

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: S = "ADOBECODEBANC", T = "ABC"

Output: "BANC"

Example 2

Input: S = "ADOBECODEBANC", T = "ABCZ"

Output: ""

Solutions

Solution 1

/**
 * 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);
    }
}

Follow up

• Minimum length substring with exactly K distinct characters - GFG
• Program to find the largest and smallest ASCII valued characters in a string - GFG