Java 9 lines concise solution with explanation


  • 0

    The idea is to keep track of number of missing characters.

    Let's run the following test case for example:
    findAnagrams("cbaebabacd", "abc")

    Here b is inclusive and e is exclusive

    b=0 e=0 missing 3
    b=0 e=1 c missing 2
    b=0 e=2 cb missing 1
    b=0 e=3 cba missing 0
    b=1 e=4 bae missing 1
    b=2 e=5 aeb missing 1
    b=3 e=6 eba missing 1
    b=4 e=7 bab missing 1
    b=5 e=8 aba missing 1
    b=6 e=9 bac missing 0
    b=7 e=10 acd missing 1

    The ones marked with "missing 0" are the answers.

        public List<Integer> findAnagrams(String s, String p) {
            int map[] = new int[1 << 7], b = 0, e = 0, missing = p.length();
            for (char c : p.toCharArray()) map[c]--; // map[c] < 0 means c is missing
            List<Integer> res = new ArrayList<>();
            while (e < s.length()) {
                if (map[s.charAt(e++)]++ < 0) missing--;
                if (e - b > p.length() && --map[s.charAt(b++)] < 0) missing++;
                if (missing == 0 && e - b == p.length()) res.add(b); 
            }           
            return res;
        } 
    

Log in to reply
 

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