CPP, beats 97% submissions


  • 0
    K
    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> result; 
            if(s.size() < p.size()) return result;
            vector<int> dict(26, 0);
            for(int i=0; i<p.size(); ++i)
                ++dict[p[i] - 'a']; 
            
            int start = 0;
            vector<int> y(26, 0); 
            for(int i=0; i<start+p.size() && start+p.size()<=s.size(); ++i){
                const char x = s[i];
                ++y[x-'a'];
                while(dict[x-'a'] < y[x-'a']){// if current count exceeds the desired count
                    const char z = s[start];
                    --y[z-'a'];
                    ++start;// keep updating start
                }
                if(i == start+p.size()-1){
                    result.push_back(start);
                    --y[s[start]-'a'];
                    ++start; 
                }
            }
                          
            return result;
        }
    };
    

Log in to reply
 

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