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

Refactored:

function findAllAnagrams(original, check) {
const anagram = []
const window = new Array(26).fill(0),
checkCounter = […window];
const a = ‘a’.charCodeAt();

for (let i = 0; i <= original.length; i++) {
    if (i < check.length) { 
        window[original.charCodeAt(i) - a]++;
        checkCounter[check.charCodeAt(i) - a]++; 
        continue;
    } 
    if (window.every((val, i) => val === checkCounter[i])) anagram.push(i - check.length)
    
    window[original.charCodeAt(i - check.length) - a]--;
    window[original.charCodeAt(i) - a]++
}

return anagram;

}

much easier to read solution in python in linear time

def get_substr(s, starting_idx, n):
“”"
args:
s (str) → whole string
starting_idx (int) → starting idx
n (int) → length of the subarray
return:
substr (str)
“”"
return s[starting_idx:starting_idx + n]

def is_anagram(s1, s2):
return sorted(s1) == sorted(s2)

def find_all_anagrams(original: str, check: str) → List[int]:
# approach - move a window of len(check) down and check if anagram
answer = []
i = 0
while i <= len(original) - len(check):
if is_anagram(get_substr(original, i, len(check)), check):
answer.append(i)
i += 1

return answer

Understood the solution far better with this refactoring. Thanks!

Much easier solution

def find_all_anagrams(s, sub_s) → List[int]:

def same_chars(s1, s2):
    return sorted(s1) == sorted(s2) and len(s1) == len(s2)

start = end = 0
pos = []

while end < len(s):
    end = min(len(s), start + len(sub_s))
    window = s[start:end]
    
    if same_chars(window, sub_s):
        pos.append(start)
    start += 1
    
return pos

I have a question:

def find_all_anagrams(original: str, check: str) → List[int]:
left = 0
right = len(check) - 1
window_check = Counter(check)
output = []
while right <= len(original) - 1:
window = set(original[left:right + 1])
if Counter(original[left:right + 1]) == window_check:
output.append(left)
left = left + 1
right = right + 1

return output

Is this solution of mine O(n) or O(n2)? I’m questioning myself since Counter is O(n), but is not done over the entire input. I’m guessing O(n) but I’m really not sure.

The scanner buffer size needs to be increased for golang code template. If the last test case if failing, add this to the main function -
maxCap := 512 * 1024
buf := make([]byte, maxCap)
scanner.Buffer(buf, maxCap)

An easier solution for Python:

offset = len(check)
ans = []

for i in range(len(original)-offset+1):
if sorted(check) == sorted(original[i:i+offset]):
ans.append(i)
return ans

Isn’t the space complexity O(n), where n is the size of original?
The solution states an O(c) space complexity, where c is the size of check, but given a large n we could append up to (n - c) + 1 anagrams to the result list.

Not that it matters much as they’re both basically O(n) space complexity, right?

Space Complexity is O(N) but N is fixed at 26 each since they are all alphabets, so this problem can be considered as O(1).

Thanks for clearing this up, I also wanted to leave a comment about this because it bothered me. It’s clearly O(1) because of the fixed size of the alphabet. :relaxed:

+1 for O((n - c) + 1) (i.e. number of anagrams). Seems like the array of indices has the potential to grow the most.

Any feedback on this :slight_smile:
`def find_all_anagrams(original: str, check: str) → List[int]:
# WRITE YOUR BRILLIANT CODE HERE
if(len(check)>len(original)):
return
checkCounter = {}
originalCounter = {}
for i in range(len(check)):
if(check[i] in checkCounter):
checkCounter[check[i]] += 1
else:
checkCounter[check[i]] = 1

    if(original[i] in originalCounter):
        originalCounter[original[i]] += 1
    else:
        originalCounter[original[i]] = 1
        

result = []
if(originalCounter == checkCounter):
    result.append(0)

for right in  range(len(check),len(original)):
    left = right - len(check)
    originalCounter[original[left]]  -=1  # remove the left 
    
    if(originalCounter[original[left]] == 0):
        originalCounter.pop(original[left])
    
    if(original[right] in originalCounter):   # add the right or increament the right
        originalCounter[original[right]] += 1
    else:
        originalCounter[original[right]] = 1
        
        
    if(originalCounter == checkCounter):
        result.append(left+1)


return result`

Cool, I produced the identical code =)) the only diff is that in C# Array.Equals does compare if instance is the same rather than compare values (I checked solution in Java), so I did own basic method for that.
Cheers

from typing import List
from collections import Counter

def find_all_anagrams(original: str, check: str) -> List[int]:
    # WRITE YOUR BRILLIANT CODE HERE
    
    original_size = len(original)
    check_size = len(check)
    check_counter = Counter(check)
    return [i for i in range(original_size) if Counter(original[i:i+check_size]) == check_counter]

:grin:

Isn’t the time complexity of this solution, O(n * k)
n → Number of elements in array.
k → Number of elements in the window.

We are looping over all elements in the array and then checking the equality of the window array and original, Since they contain k number of element, won’t the complexity be O(n * k) ?

In my understanding the amount of keys in the maps is at most 26, so it’s constant and can be omitted so it ends up at O(N)

I’m so confused by the first test case and think it may be broken or buggy somehow.
This code works for all other test cases except for test #1, but it WORKS for the same test input on LeetCode:

from typing import List
from collections import Counter

def find_all_anagrams(original: str, check: str) → List[int]:

anagram_indexes = []

check_size = len(check)
check_ctr = Counter(check)
window_ctr = Counter(original[:check_size])

if check_ctr == window_ctr:
    anagram_indexes.append(0)

for i in range(check_size, len(original)):
    window_ctr[original[i-check_size]] -= 1
    window_ctr.update([original[i]])
    
    if check_ctr == window_ctr:
        anagram_indexes.append(i - check_size + 1)
        
return anagram_indexes