7-line C++ O(Ns+Np) one pass sliding window solution (detailed explanation)


  • 0

    Sliding Window Algorithm:

    • Initialize hashmap freq to be char frequency count of string p;
    • Maintaining a sliding window of size p.size() in string s, and decrement char frequency from freq if associated char is detected in s, remove entry from freq if whenever frequency becomes 0;
    • Record initial index i to result whenever freq becomes empty.
        vector<int> findAnagrams(string s, string p) {
          unordered_map<char, int> freq; for (char c:p) freq[c]++;
          int np = p.size(); vector<int> res;
          for (int i = 0; i < s.size(); ++i) {
            if (!--freq[s[i]]) freq.erase(s[i]);
            if (i >= np && !++freq[s[i-np]]) freq.erase(s[i-np]);
            if (freq.empty()) res.push_back(i-np+1);
          }
          return res;
        }
    

Log in to reply
 

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