Accepted Java Solution


  • 0
    M
        public String minWindow(String s, String t) {
            Set<Character> set = new HashSet<>();
            Map<Character, Integer> map = new HashMap<>();
            int cnt = 0;
            int lo = 0, hi = 0, start = 0;
            int minLen = Integer.MAX_VALUE;
            for (char c : t.toCharArray()) {
                set.add(c);
                if (map.containsKey(c)) map.put(c, map.get(c) + 1);
                else map.put(c, 1);
                ++cnt;
            }
            while (hi < s.length()) {
                char c = s.charAt(hi);
                if (set.contains(c)) {
                    int num = map.get(c);
                    if (num > 0) --cnt;
                    map.put(c, --num);
                }
                ++hi;
                while (cnt == 0) {
                    if (hi - lo < minLen) {
                        minLen = hi - lo;
                        start = lo;
                    }
                    c = s.charAt(lo);
                    if (set.contains(c)) {
                        int d = map.get(c);
                        if (d == 0) ++cnt;
                        map.put(c, d + 1);
                    }
                    ++lo;
                }
            }
            return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start  + minLen);
        }
    

    This solution refers to https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems


Log in to reply
 

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