C++ O(n) Solution, Two Pointers


  • 2
    J

    Use two pointers to track down the current window's status.

    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> ans;
            if(p.empty() || s.empty()) return ans;
    
            int cnt[256] = {0};
            for(char ch : p) cnt[ch] ++;
            
            int lf = 0, rt = 0;
            while(rt < s.size()) {
                cnt[s[rt]] --;
                while(lf <= rt && cnt[s[rt]] < 0) {
                    cnt[s[lf ++]] ++;
                }
                if(rt - lf + 1 == p.size()) {
                    ans.push_back(lf);
                    cnt[s[lf ++]] ++;
                }
                rt ++;
            }
            return ans;
        }
    };
    

Log in to reply
 

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