LeetCode Solutions
438. Find All Anagrams in a String
Time: $O(n)$ Space: $O(26)$
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
vector<int> count(128);
int required = p.length();
for (const char c : p)
++count[c];
for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s[r]] >= 0)
--required;
while (required == 0) {
if (r - l + 1 == p.length())
ans.push_back(l);
if (++count[s[l++]] > 0)
++required;
}
}
return ans;
}
};
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
int[] count = new int[128];
int required = p.length();
for (final char c : p.toCharArray())
++count[c];
for (int l = 0, r = 0; r < s.length(); ++r) {
if (--count[s.charAt(r)] >= 0)
--required;
while (required == 0) {
if (r - l + 1 == p.length())
ans.add(l);
if (++count[s.charAt(l++)] > 0)
++required;
}
}
return ans;
}
}
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
count = Counter(p)
required = len(p)
for r, c in enumerate(s):
count[c] -= 1
if count[c] >= 0:
required -= 1
if r >= len(p):
count[s[r - len(p)]] += 1
if count[s[r - len(p)]] > 0:
required += 1
if required == 0:
ans.append(r - len(p) + 1)
return ans