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
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)
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.
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.
Any feedback on this
`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]
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) ?
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