yet another java Accepted O(n) solution


  • 0
    S
    public String minWindow(String s, String t) {
            int smallestWindowLength = Integer.MAX_VALUE;
            String smallestWindowString = "";
            Map<Character, Integer> tMap = fillMe(t);
            Map<Character, Integer> sMap = new HashMap<>();
            int found = 0;
    
            int head = -1, tail = -1, cWL = 0;
            for (int i = 0; i < s.length(); i ++) {
                if (tMap.containsKey(s.charAt(i)) && tMap.get(s.charAt(i)) > 0) {
                    if (head == -1) {
                        head = i; tail = i;
                        if (t.length() == 1) {
                            return s.charAt(i) + "";
                        } else {
                            sMap.put(s.charAt(i), 1);
                        }
                        found ++;
                    } else {
                        tail = i;
                        sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
                        if (tMap.get(s.charAt(i)) >= sMap.get(s.charAt(i))) {
                            found ++;
                        }
                        while (found == t.length()) {
                            cWL = tail - head + 1;
                            if (cWL < smallestWindowLength) {
                                smallestWindowLength = cWL;
                                smallestWindowString = s.substring(head, tail + 1);
                            }
                            if (tMap.getOrDefault(s.charAt(head), 0) > 0) {
                                sMap.put(s.charAt(head), sMap.get(s.charAt(head)) - 1);
                                if (sMap.get(s.charAt(head)) < tMap.get(s.charAt(head))) {
                                    found --;
                                }
                            }
                            head ++;
                        }
                    }
                }
            }
            return smallestWindowString;
        }
    
        Map<Character, Integer> fillMe(String t) {
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < t.length(); i ++) {
                if (map.containsKey(t.charAt(i))) {
                    map.put(t.charAt(i), map.get(t.charAt(i)) + 1);
                } else {
                    map.put(t.charAt(i), 1);
                }
            }
            return map;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.