Leetcode 438 : Find all angagrams in string
This is program for finding all anagrams in string. It beats all leetcode solution in speed , running at 39 ms , seems to be below the 58ms bucket.
https://leetcode.com/problems/find-all-anagrams-in-a-string/
Natively it will run much faster
Python program to find all anagrams in string
# more optimized version and explanation here
# https://www.computerscienceai.com/2026/07/leetcode-438-find-all-angagrams-in-string.html
from itertools import islice
from collections import Counter
class Solution:
# changed var s to si
def findAnagrams(self, si: str, p: str) -> List[int]:
if len(p) > len(si) :
return []
# solution 1
""" 8975 ms Beats 5.01% Memory 20.00 MB Beats 15.33% """
"""
n = len(p); indices = []; pc = Counter(memoryview(p.encode("ascii"))) # comedy on this line :)
view=memoryview(s.encode("ascii"))
for i in range(0 , len(s)):
#print(pc)
#print(Counter(view[i:i+n].tobytes() ))
if Counter(view[i:i+n].tobytes() ) == pc :
indices.append(i)
return indices
"""
# solution 2
""" 8037 ms Beats 5.01% Memory 19.82 MB Beats 41.41% """
#n = len(p); sie = len(si) ; indices = []; pc = Counter(p) # comedy on this line :)
# worst solution , it was passing with string slicing
"""
for i in range(0 , len(si)):
#print(pc)
#print(Counter(view[i:i+n].tobytes() ))
sc = Counter()
for j in range(i , i + n if i + n < sie else sie ) :
sc[si[j]] += 1
#print(sc)
if sc == pc :
indices.append(i)
return indices
"""
# solution 3
""" 361 ms Beats 11.51% | Memory 19.87 MB Beats 41.41% """
# Runtime 39 ms Beats 61.73% Memory 19.97 MB Beats 15.33%
# this beats the top solution here one without data structures
# WIN
# this is one pass processing , still too slow
pc = Counter(p); indices = [] ; n = len(p) ; lo = 0 ; pc_l = set(p) ;
min_len = n if n < len(si) else len(si)
isl = Counter()
# found key
matches = 0
for ch in islice( si , 0 , min_len ):
isl[ch] += 1
#print(isl )
#print(+pc , "\n") ;
#print(i)
if ch in pc_l :
if pc[ch] == isl[ch ]:
matches += 1
# if matches is same its match
if matches == len(pc) :
indices.append(lo)
lch = si[0]
if lch in pc_l and pc[lch ] == isl[lch ] :
matches -=1
isl[si[0]] -= 1 ; #print(isl)
for i , ch in enumerate( islice( si , n , None ) , start = n ) :
lo = i + 1 - len(p);
lch = si[ lo ]
isl[ch] += 1
#print(isl )
#print(+pc , "\n") ;
#print(i)
if ch in pc_l :
if pc[ch] == isl[ch ] :
matches += 1
if matches == len(pc) :
indices.append(lo)
if lch in pc_l and pc[lch] == isl [lch]:
matches -= 1
isl[ lch ] -= 1
return indices
Comments