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;
}
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