C++ O(N) sliding window (looking for advice on how to improve run time)


  • 0
    G
    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) 
        {
            vector<int> PCount(26,0);
            vector<int> SCount(26,0);
            vector<int> Res;
            
            for(auto &c: p)
            {
                PCount[c - 'a']++;
            }
            
            int Count = 0;
            
            int j = 0;
            
            for(int i = 0; i <= (int)s.size() - (int)p.size();)
            {
                
                while(PCount[s[j] - 'a'] > 0 && Count < p.size())
                {
                    if(SCount[s[j] - 'a'] < PCount[s[j] - 'a'])
                    {
                        SCount[s[j] - 'a']++;
                        Count++;
                    }
                    else
                    {   
                        Count = 0;
                        break;
                    }
                    
                    j++;
                }
                
                if(Count == p.size())
                {
                    Res.push_back(i);
                    Count--;
                    SCount[s[i] - 'a']--;    
                    i++;
                    
                }
                else
                {
                    Count = 0;
                    SCount = vector<int>(26,0);
                    i++;
                    j = i;
                }
            }
            
            return (Res);
        }
    };
    

Log in to reply
 

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