Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Pseudocode
- don't understand how solution was formed
- why uniqueChar?
Solution
// from solutions
// https://leetcode.com/problems/find-all-anagrams-in-a-string/solutions/592384/sliding-window-explanation-javascript-solution-w-comments-faster-than-100/
// previous naive approach had TC O(s^2)
// dumbing down logic to find uniqueChars then following up with starting index, simplified the looping operation.
var findAnagrams = function (s, p) {
const freqMap = {};
let result = [];
let uniqueChar = 0;
let i = 0;
let j = 0;
for (let i = 0; i < p.length; i++) {
if (!freqMap[p[i]]) {
freqMap[p[i]] = 0;
uniqueChar++;
}
freqMap[p[i]]++;
}
while (j < s.length) {
// console.log('out', i, j)
let char = s[j];
if (freqMap[char] !== undefined) {
freqMap[char] -= 1;
if (freqMap[char] === 0) {
// all occurance of unique letters is found until this end (j)
uniqueChar--;
}
}
j++;
while (uniqueChar === 0) {
// console.log('in', i, j)
let temp = s[i];
if (freqMap[temp] !== undefined) {
// yep, we've found the char, re-instate it for the next find
freqMap[temp] += 1;
if (freqMap[temp] > 0) {
uniqueChar++;
}
}
if (j - i === p.length) {
result.push(i);
}
i++;
}
}
return result;
};
