C++ O(n) sliding window solution


  • 0
    Y
    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> res;
            if (s.size() < p.size()) return res;
            
            int n = s.size(), k = p.size(), cnt[26] = {}, i = 0;
            for (char c : p) cnt[c - 'a']++;
            
            for (int j = 0; j < n; j++) {
                int idx = s[j] - 'a';
                if (--cnt[idx] >= 0) {
                    k--;
                }
                else {
                    while (cnt[idx] < 0) { // do not allow negative cnt, fix it immediately
                        if (++cnt[s[i++] - 'a'] > 0) k++;
                    }
                }
                
                if (k == 0) res.push_back(i);
            }
            
            return res;
        }
    };
    

Log in to reply
 

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