Concise C++ sliding window solution


  • 0
    H

    i is the right position of the window and start is the left position. With i moving on, reduce the counter of corresponding characters.
    Once not possible to form p with characters in current window after i moved to a new position, we narrow down the window width by moving start forward. With start moving on, increase the counter of each character until s[start] == s[i], i.e. transfer the credit of s[start] to s[i]

    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> m(26);
            for (auto c : p) m[c-'a']++; 
            int start = 0;
            vector<int> res;
            for (int i = 0; i < s.size(); i++) {
                if (m[s[i]-'a']) {
                    m[s[i]-'a']--; 
                }
                else {
                    while(s[start] != s[i]) m[s[start++]-'a']++;
                    start++;
                }
                if (i - start + 1 == p.size()) {
                    res.push_back(start);
                }
                if (s.size() - start < p.size()) break;
            }
            return res;
        }
    };
    

Log in to reply
 

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