Find All Anagrams in a String

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".

Solution

Solution 1: Naive (Time exceed solution)

class Solution:
    
    def isAnagram(self, s, p):
        counter = [0] * 26
        
        for letter in p:
            counter[ord(letter) - ord("a")] += 1
        
        for letter in s:
            counter[ord(letter) - ord("a")] -= 1
            if counter[ord(letter) - ord("a")] < 0:
                return False
        return True
    
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # r = len(res)
        # l = len(p)
        # Time complexity: O(n * l)
        # Space complexity: O(26 + r) ~= O(1)
        res = []
        m, n = len(s), len(p)
        for i in range(m-n+1):
            if self.isAnagram(s[i:i+n], p):
                res.append(i)
        return res

Solution 2: Naive 2

class Solution:
    
    def isAnagram(self, s, p):
        if "".join(sorted(s)) == p:
            return True
        else:
            return False
        
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # Time complexity: O(n * log(n))
        # Space complexity: O(26 + r) ~= O(1)
        
        anagram = "".join(sorted(p))
        m, n, res = len(s), len(p), []
        for i in range(m-n+1):
            if self.isAnagram(s[i:i+n], anagram):
                res.append(i)
        return res

Solution 3: Dynamic variant + hashmap

class Solution:
       
    def build_hashmap(self, s):
        hashmap = {}
        for letter in s:
            if letter not in hashmap:
                hashmap[letter] = 1
            else:
                hashmap[letter] += 1
        return hashmap
    
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # Time complexity: O(n * len(P)) ~= O(n).
        # Space complexity: O(len(s) + len(p)).
        
        m, n, res = len(s), len(p), []
        
        # Build hashmap of p.
        hashmapP = self.build_hashmap(p)
        
        for beg in range(m-n+1):    
            if beg == 0:
                # Build hashmap of s.
                hashmapS = self.build_hashmap(s[:n])
            else:
                # In dynamic variant, Remove value at left side of window.
                hashmapS[s[beg-1]] -= 1
                
                # Take into account new right side of window.
                if s[beg+n-1] in hashmapS:
                    hashmapS[s[beg+n-1]] += 1
                else:
                    hashmapS[s[beg+n-1]] = 1
            
            # Compare the 2 hashmaps to know whether s and p are anagrams or not.
            tmp = 0
            for letter in hashmapP:
                # Count only letters who belong in both hashmaps.
                if letter in hashmapS and hashmapS[letter] == hashmapP[letter]:
                    tmp += hashmapS[letter] 
        
            if tmp == sum(hashmapP.values()):
                res.append(beg)

        return res

Solution 4: Dynamic variant + hashmap (but using Counter())

from collections import Counter

class Solution(object):
    def findAnagrams(self, s, p):

        m, n = len(s), len(p)
        # Convert list of anagram letters to a Counter (hashtable)
        countP = Counter(p)  
        ans = []  
        window = None
        
        for i in range(0,m-n+1):
            if i == 0: 
                # Initialize window with beginning of s => length = length of anagram letters
                window = Counter(s[:n])   
            else:       
                # Move window to right: 1. remove character on the left
                window[s[i-1]] -= 1
                # 2. add character on the right
                window[s[i+n-1]] += 1 
            
            # Check if window is anagram (direct comparison of counters does not work with 0 entries)
            if len(window - countP) == 0:
                ans.append(i)
                
        return ans