LeetCode - Minimum Window Substring

Problem description

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).

Example:

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

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.

Analysis

Generally, it’s a typical sliding window problem.

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        
        for (char c:t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)  +1);
        }
        
        int end = 0;
        String res = "";
        int start = 0;
        
        while (end < s.length()){
            char c = s.charAt(end);
            
            if (map.containsKey(c)){
                map.put(c, map.get(c) - 1);
            }
            
            end++;
            
            while (check(map) && start <= end){
                String r = s.substring(start, end);
                
                if (r.length() < res.length() || res.length() == 0){
                    res = r;
                }
                    
                char c2 = s.charAt(start);
                if (map.containsKey(c2)){
                    map.put(c2, map.get(c2) + 1);
                }
                start++;
            }
        }
        
        return res;
    }
    
    boolean check(HashMap<Character, Integer> map){
        for (Map.Entry<Character, Integer> entry: map.entrySet()){
            if (entry.getValue() > 0){
                return false;
            }
        }
        
        return true;
    }
}

What to improve

• should be more familiar with the template of sliding window.