Find All Anagrams in a String LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> findAnagrams(string s, string p) {
4
    vector<int> pv(26, 0), sv(26, 0), res;
5
    if (s.size() < p.size()) return res;
6
    // fill pv, vector of counters for pattern string and sv, vector of counters
7
    // for the sliding window
8
    for (int i = 0; i < p.size(); ++i) {
9
      ++pv[p[i] - 'a'];
10
      ++sv[s[i] - 'a'];
11
    }
12
    if (pv == sv) res.push_back(0);
13

14
    // here window is moving from left to right across the string.
15
    // window size is p.size(), so s.size()-p.size() moves are made
16
    for (int i = p.size(); i < s.size(); ++i) {
17
      // window extends one step to the right. counter for s[i] is incremented
18
      ++sv[s[i] - 'a'];
19

20
      // since we added one element to the right,
21
      // one element to the left should be discarded.
22
      // counter for s[i-p.size()] is decremented
23
      --sv[s[i - p.size()] - 'a'];
24

25
      // if after move to the right the anagram can be composed,
26
      // add new position of window's left point to the result
27
      if (pv == sv) // this comparison takes O(26), i.e O(1), since both vectors
28
                    // are of fixed size 26. Total complexity O(n)*O(1) = O(n)
29
        res.push_back(i - p.size() + 1);
30
    }
31
    return res;
32
  }
33
};