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;
            }
        }
    }
    
  • Todo
    
  • from collections import Counter
    
    
    class Solution(object):
      def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        sCount = Counter(s[:len(p) - 1])
        pCount = Counter(p)
        ans = []
    
        for i in range(len(p) - 1, len(s)):
          sCount[s[i]] += 1
          if sCount == pCount:
            ans.append(i - len(p) + 1)
          sCount[s[i - len(p) + 1]] -= 1
          if sCount[s[i - len(p) + 1]] == 0:
            del sCount[s[i - len(p) + 1]]
        return ans
    
    

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;
        }
    }
    
  • Todo
    
  • from collections import Counter
    
    
    class Solution(object):
      def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        sCount = Counter(s[:len(p) - 1])
        pCount = Counter(p)
        ans = []
    
        for i in range(len(p) - 1, len(s)):
          sCount[s[i]] += 1
          if sCount == pCount:
            ans.append(i - len(p) + 1)
          sCount[s[i - len(p) + 1]] -= 1
          if sCount[s[i - len(p) + 1]] == 0:
            del sCount[s[i - len(p) + 1]]
        return ans
    
    

All Problems

All Solutions