Sliding Window in Java, very similar to Find All Anagrams in a String


  • 2
    F

    Let's take a look at a solution using sliding window in Find All Anagrams in a String( https://leetcode.com/problems/find-all-anagrams-in-a-string/#/description )

        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<Integer>();
            if(s == null || s.length() == 0 || p == null || p.length() == 0) return res;
            int begin = 0, end = 0;
            Map<Character, Integer> map = new HashMap<>();
            for(char c : p.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            int counter = map.size();
            while(end < s.length()){
                char ch = s.charAt(end);
                if(map.containsKey(ch)) {
                    map.put(ch, map.get(ch) - 1);
                    if(map.get(ch) == 0) {
                        counter--;
                    }
                }
                while(counter == 0) {
                    if(end - begin + 1 == p.length()) { 
                        res.add(begin);
                    }
                    char temp = s.charAt(begin);
                    if(map.containsKey(temp)) {
                        map.put(temp, map.get(temp) + 1);
                        if(map.get(temp) > 0) {
                            counter++;
                        }
                    }
                    begin++;
                }
                end++;
            }
            return res;
    }
    

    Then is my solution for this problem, it's a little bit long but this template can be applied to a lot of problems.

        public boolean checkInclusion(String s1, String s2) {
            if(s1 == null || s2 == null) {
                return false;
            }
            int len = s1.length();
            Map<Character, Integer> map = new HashMap<>();
            for(char c : s1.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            int count = map.size();
            int begin = 0;
            int end = 0;
            while(end < s2.length()) {
                char ch = s2.charAt(end);
                if(map.containsKey(ch)) {
                    map.put(ch, map.get(ch) - 1);
                    if(map.get(ch) == 0) {
                        count--;
                    }
                }
                while(count == 0) {
                    if(end - begin + 1 == len) {
                        return true;
                    }
                    char temp = s2.charAt(begin);
                    if(map.containsKey(temp)) {
                        map.put(temp, map.get(temp) + 1);
                        if(map.get(temp) > 0) {
                            count++;
                        }
                    }
                    begin++;
                }
                end++;
            }
            return false;
        }
    

    Similar problems:

    Minimum window substring
    Longest Substring without Repeating Characters
    Longest Substring with at most 2 Distinct Characters
    Longest Substring with at most k Distinct Characters

    hope this helps!


  • 0
    J

    Compared with other solutions that uses Arrays.equals or ..
    This is more natural and easier to think and prove it during interview.


Log in to reply
 

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