Java

import java.util.ArrayList;
import java.util.List;

/**

 Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

 Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

 The order of output does not matter.

 Example 1:

 Input:
 s: "cbaebabacd" p: "abc"

 Output:
 [0, 6]

 Explanation:
 The substring with start index = 0 is "cba", which is an anagram of "abc".
 The substring with start index = 6 is "bac", which is an anagram of "abc".

 Example 2:

 Input:
 s: "abab" p: "ab"

 Output:
 [0, 1, 2]

 Explanation:
 The substring with start index = 0 is "ab", which is an anagram of "ab".
 The substring with start index = 1 is "ba", which is an anagram of "ab".
 The substring with start index = 2 is "ab", which is an anagram of "ab".

 */

public class Find_All_Anagrams_in_a_String {

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            if (p == null || s == null || s.length() < p.length()) return res;
            int m = s.length(), n = p.length();
            for (int i = 0; i < m-n+1; i++) {
                String cur = s.substring(i, i+n);
                if (helper(cur, p)) {
                    res.add(i);
                }
            }
            return res;
        }
        public boolean helper(String a, String b) {

            if (a == null || b == null || a.length() != b.length()) {
                return false;
            }

            int[] dict = new int[26];

            // 2*logN is better than sorting 2*NlogN
            for (int i = 0; i < a.length(); i++) {
                char ch = a.charAt(i);
                dict[ch-'a']++;
            }

            for (int i = 0; i < b.length(); i++) {
                char ch = b.charAt(i);
                dict[ch-'a']--;
                if (dict[ch-'a'] < 0) return false;
            }

            return true;
        }
    }
}

Java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> indices = new ArrayList<Integer>();
        if (s == null || p == null || s.length() < p.length())
            return indices;
        int sLength = s.length();
        int pLength = p.length();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLength; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (match(sCount, pCount))
            indices.add(0);
        for (int i = pLength; i < sLength; i++) {
            char prevC = s.charAt(i - pLength), curC = s.charAt(i);
            sCount[prevC - 'a']--;
            sCount[curC - 'a']++;
            if (match(sCount, pCount))
                indices.add(i - pLength + 1);
        }
        return indices;
    }

    public boolean match(int[] sCount, int[] pCount) {
        for (int i = 0; i < 26; i++) {
            if (sCount[i] != pCount[i])
                return false;
        }
        return true;
    }
}

All Problems

All Solutions