Find All Anagrams in a String - Two Pointers / Sliding Window

https://algo.monster/problems/find_all_anagrams

def get_mapping(check):
mapping = {}
for char in check:
if char in mapping:
mapping[char] += 1
else:
mapping[char] = 1
return mapping

def valid_anagram_window(window):

for value in window.values():
    if value != 0:
        return False

return True

def find_all_anagrams(original, check):

left = 0
result = []
right = len(check)

invalid_input = lambda x, y: len(y) > len(x)

if invalid_input(original, check):
    return []

while left < len(original) - right + 1:

    window = original[left:left+right]
    mapping = get_mapping(check)
    for char in window:
        if char in mapping:
            mapping[char] -= 1
        else:
            continue

    if valid_anagram_window(mapping):
        result.append(left)

    left += 1

return result

def find_all_anagrams(original: str, check: str) → List[int]:
def isAnagram(word1, word2):
# word2 should be sorted already
return sorted(word1) == word2

left = 0
right = len(check) 
res = []
check = sorted(check)

while right <= len(original):
    if isAnagram(original[left:right], check):
        res.append(left)
    
    right += 1
    left += 1
     

return res

My python solution:

from typing import List
from collections import Counter

def find_all_anagrams(original: str, check: str) → List[int]:
if len(check) > len(original): return []
check_counter = Counter(check)
l,r=0, len(check)-1
ans = []
word_counter = Counter(original[:r])
while r < len(original):
word_counter[original[r]] = 1 + word_counter.get(original[r], 0)
if word_counter == check_counter:
ans.append(l)
word_counter[original[l]] -= 1
if word_counter[original[l]] == 0: del word_counter[original[l]]
l += 1
r += 1
return ans

def isAnagram(w1, w2):
if sorted(w1) == sorted(w2):
return True
else:
return False

def find_all_anagrams(original: str, check: str):
# WRITE YOUR BRILLIANT CODE HERE
res = list()
start, end = 0, len(check)
while end <= len(original):
#print(original[start:end], check)
if isAnagram(original[start:end], check): #simple set equal is not enough!
res.append(start)
start += 1
end += 1
return res

from typing import List

def find_all_anagrams(original: str, check: str) → List[int]:
# WRITE YOUR BRILLIANT CODE HERE
left, right = 0, len(check)
n = len(original)
res = []

while right <= n:
    if right - left == len(check):
        if sorted(original[left:right]) == sorted(check):
            res.append(left)
    left += 1        
    right += 1
return res

those comments are there for your understanding of the code. so you understand what each line is trying to do. in an interview obviously you dont write it, you just explain to your interviewer what you’re trying to do

What would be the time complexity of such a loop that keeps sorting elements to check values?

My solution works on LeetCode for the same case(Test #1) but fails here. I always gets “0” in the output instead of “0 6” while running same in LC, it works just fine.

def find_all_anagrams(original: str, check: str) -> List[int]:
    # WRITE YOUR BRILLIANT CODE HERE
    right = 0
    anagram = Counter(check)
    lenCheck = len(check)
    result = []
        

    while right < len(original) - lenCheck + 1:
        if right == 0:
            tempCounter = Counter(original[right:lenCheck])
        else:            
            tempCounter[original[right-1]] -= 1
            tempCounter[original[right+lenCheck-1]] += 1
            
        if anagram == tempCounter:
            result.append(right)
            print(tempCounter,right )
        right += 1
                
    return result

I think the issue here is Counter comparison in different python versions. LC and AM likely have different versions.

Changed in version 3.10: In equality tests, missing elements are treated as having zero counts. Formerly, Counter(a=3) and Counter(a=3, b=0) were considered distinct.

For test case 1 and right = 6, tempCounter is Counter({'c': 1, 'b': 1, 'a': 1, 'e': 0}) and anagram is Counter({'a': 1, 'b': 1, 'c': 1})

anagram == tempCounter would return different result depending on the python version.

I’ve found using a separate class to manage the sliding window makes the impl easy to understand, FYI this is my code:

  def __init__(self):
    self.container = defaultdict(lambda: 0)
    
  def push(self, c):
    self.container[c] += 1
    
  def pop(self, c):
    self.container[c] -= 1
    if self.container[c] == 0:
        self.container.pop(c)
    
  def size(self):
    return sum(self.container.values())
    
    
def find_all_anagrams(original: str, check: str) -> List[int]:
    # WRITE YOUR BRILLIANT CODE HERE
    target_dict = Counter(check)
    fast = slow = 0
    res = []
    window = SlidingWindow()
    win_size = len(check)
    while fast < len(original):
        c = original[fast]
        window.push(c)
        #print(f"checking {c}, win: {window.container}")
        if window.size() == win_size:
            #print(f"window is full: {win_size}")
            if window.container == target_dict:
                #print("hit a match")
                res.append(slow)
            # window is full, pop the leftmost char
            window.pop(original[slow])
            #print(f"popped {original[slow]}, window is moved: {window.container}")
            slow += 1
        fast += 1
    return res```

My solution, using Counter() to for anagrams checking.

def find_all_anagrams(original: str, check: str) → List[int]:
def is_anagrams(s1, s2):
return Counter(s1) == Counter(s2)

check_set = [c for c in check]
window_set = [c for c in original[:len(check_set)]]
res = []
for i in range(len(check_set), len(original)+1):
    if is_anagrams(check_set, window_set): 
        res.append(i - len(check_set))
    if i < len(original):
        window_set.append(original[i])
        window_set.pop(0)

return res

Javascript using Maps to keep count of letter frequency.
No need to iterate over 2 arrays to validate equality

function findAllAnagrams(original, check) {
const checkMap = getFreqMap(check);
const windowMap = new Map();

let l = 0;
const checkLength = check.length;
let matchLength = 0;
const res = [];

if(original.length < checkLength) return [];

for(let r = 0; r < original.length; r++) {
    // is window length reached?
    if(r - l  > checkLength - 1) {
        const leftChar = original.charAt(l); 
        // leftSubstract
        if(windowMap.has(leftChar)) {
            const count = windowMap.get(leftChar) - 1; 
            windowMap.set(leftChar, count);
            if(count < checkMap.get(leftChar)) matchLength -= 1;
        }
        
        l += 1;
    }

    // right Add
    const rightChar = original.charAt(r);
    if(checkMap.has(rightChar)) {
        if(!windowMap.has(rightChar)) windowMap.set(rightChar, 0);
        const count = windowMap.get(rightChar) + 1; 
        windowMap.set(rightChar, count);
        if(count <= checkMap.get(rightChar)) matchLength += 1;
        if(matchLength === checkLength) res.push(l);
    }
}

return res;

}

LC: https://leetcode.com/problems/find-all-anagrams-in-a-string/

Python solution:

`def is_anagrams(s1: str, s2: str):
return Counter(s1) == Counter(s2)

def find_all_anagrams(original: str, check: str) → List[int]:
check_set = [c for c in check]
window_set = []
indexes = []

for i in range(len(original)): 
    if len(window_set) < len(check_set):
        window_set.append(original[i])
        
    if len(window_set) == len(check_set):
        if is_anagrams(check_set, window_set):
            indexes.append(i - len(check_set) + 1)
        window_set.pop(0)
                  
return indexes

`

Thought solution in example was overly complex here’s mine, O(n) & O(1)
def getCount(arr):
res = {}
for el in arr:
if el in res:
res[el] += 1
else:
res[el] = 1
return res

def find_all_anagrams(original: str, check: str) → List[int]:
currWindow = []
result = []
slow = 0

for fast in range(len(original)):
    currWindow.append(original[fast])
    
    if getCount(currWindow) == getCount(check):
        result.append(slow)
        currWindow.pop(0)
        slow += 1
        
    if len(currWindow) == len(check):
        currWindow.pop(0)
        slow += 1
          
return result

My c++ code

std::vector find_all_anagrams(std::string original, std::string check) {
// check_length is the window size
int original_length = original.length(), check_length = check.length();
if (original_length < check_length) return {};

std::vector<int> res;
// stores the frequency of each character in the check string
std::unordered_map<char, int> check_counter;
// stores the frequency of each character in the current window
std::unordered_map<char, int> window;
// first window
for (int i = 0; i < check_length; i++) {
    //check_counter[check[i] - 'a']++;
    //window[original[i] - 'a']++;
    check_counter[check[i]]++;
    window[original[i]]++;
}
if (window == check_counter) res.emplace_back(0);

for (int i = check_length; i < original_length; i++) {
    window[original[i - check_length]]--;
    window[original[i]]++;
    if (window == check_counter) {
        res.emplace_back(i - check_length + 1);
    }
}
return res;

}

except first test case, all other test cases are passing. Can anyone explain why first test case is not passing?

This works find for me in JavaScript:

function findAllAnagrams(original, check) {
// WRITE YOUR BRILLIANT CODE HERE
if (original.length < check.length) return [];

let arrayCheck = new Array(26).fill(0);
let arrayOriginal = Array(26).fill(0);

let aCharCode = 'a'.charCodeAt(); // Convert Initial A to number for index calculation

for (let i = 0; i < check.length; i++){
    arrayCheck[check.charCodeAt(i) - aCharCode]++;
}

let fast = slow = 0, result = [];

while (fast <= original.length){
    if ((fast - slow) === check.length){
        
        if (equals(arrayCheck, arrayOriginal)){
            result.push(slow);
        } 
        arrayOriginal[original.charCodeAt(slow++) - aCharCode]--;
        
    } else {
        arrayOriginal[original.charCodeAt(fast++) - aCharCode]++;
  }
}

return result;

}

function equals(arr1, arr2) {
return arr1.length === arr2.length && arr1.every((val, i) => val === arr2[i]);
}

I like your answer. Additionally you could write the getCount function like that (nothing major, just a shortcut):
def getCount(arr):
res = {}
for el in arr:
res[el] = res.get(el, 0) + 1
return res