Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Example:
- s = "cbaebabacd", p = "abc"
- s = "abab", p ="ab"
This problem looks like basic looping and checking whether the sub array of s contains p, But the problem is p's length is greater than 20000, which will result in Time Limit Exceeded(TLE)
I will go through two approaches
- Basic looping and checking
- Storing p in a hashMap and using sliding window technique
Basic Looping and checking Algorithm
- Create a result array and store length of s and p strings in variables
- Now Loop through s
- At i th index of s check if p has s[i]
- inside the if condition create a temp variable which is equal to p (this will be used to check by popping out matched character) and a boolean variable cur
- Now loop through j which is initially equals to i and less than i + pLen
- if temp does not contain
s[j]
break out of the loop and change cur tofalse
- else, pop
s[j]
from temp - After for loop check cur, if it's true push i
Here's the code
var findAnagrams = function(s, p) {
let res = new Array()
let sLen = s.length, pLen = p.length
for(let i = 0; i< sLen; i++) {
if(p.includes(s[i])) {
let temp = p, cur = true
for(let j = i; j < i + pLen; j++) {
if(!temp.includes(s[j])) {
cur = false
break
} else {
let tempIdx = temp.indexOf(s[j])
temp = temp.slice(0, tempIdx) + temp.slice(tempIdx + 1)
}
}
if(cur) {
res.push(i)
}
}
}
return res
};
In the above algorithm we are almost constantly looping through every index of s checking anagram of p exists or not
Sliding Window Technique
This technique id used mostly on strings, arrays, linked lists (basically iterables) and you need to find min, max, or contains
If you observe we are asked to check s contains anagrams of p
So Here's the algorithm:
- Create two variables start and end
- First store all the characters of p in a hash map with value as number of occurences
- while end < s.length
-
if hashMap of s[end] is greater than 0, subtract 1 from it and increase end
inside the same if check end - start is equal to pLenif it's pLen, push start to result array
else if start equals to end increment both start and end
else increment start and add 1 to hashMap of s[start]
Here's the code
var findAnagrams = function(s, p) {
let hashMap = new Map()
for(let i = 0; i < p.length; i++) {
if(hashMap.has(p[i])) {
hashMap.set(p[i], hashMap.get(p[i]) + 1)
} else {
hashMap.set(p[i], 1)
}
}
let res = new Array()
let start = 0, end = 0
while(end < s.length) {
if(hashMap.get(s[end]) > 0) {
hashMap.set(s[end], hashMap.get(s[end]) - 1)
end++
if(end - start == p.length) {
res.push(start)
}
} else if(start == end) {
start++
end++
} else {
hashMap.set(s[start], hashMap.get(s[start]) + 1)
start++
}
}
return res
};
Top comments (0)