# A solution that really runs in O(n)

• I've seen some discussions claiming they are O(n) while they are not.
It is expensive to compare two whole vectors every time.
This is my solution, that does run in O(n).
If you feel panaroic, you can check if each match is truly a match,
though it is kind of unnecessary IMO.

``````class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
int N = s.size();
int P = p.size();
if (N < P) return result;

// Initial rand values
vector<unsigned> rand_val(26);
for (int i = 0; i < 26; i++) rand_val[i] = rand();

// Target for matching
unsigned target = 0;
for (char c : p) target += rand_val[c - 'a'];

// sum[i] : sum of hash for s[0], s[1], ..., s[i]
vector<unsigned> sum(N);
sum[0] = rand_val[s[0] - 'a'];
for (int i = 1; i < N; i++) sum[i] = sum[i - 1] + rand_val[s[i] - 'a'];

// Check all possible hash sums
for (int i = P; i <= N; i++) {
unsigned diff = sum[i - 1];
if (i != P) diff -= sum[i - P - 1];

if (diff == target) {
// If you feel panaroic you can explicitly check the string,
// in case of hash collision
result.push_back(i - P);
}
}
return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.