C++ (9ms) solution with minimized computations.


  • 0
    L

    My goal when working on this solution was to minimize bookkeeping overhead.
    It uses a sliding window and a single array of 26 ints, named distance. This buffer is kept up to date with at most a single increment and decrement each iteration.

    At the start of each iteration:

    • The size of the window is equal to the size of the needle
    • distance[X] == (count of X in needle) - (count of X in window), for all X in [a-z]
    • If distance contains only zeros then the window is a permutation of the needle.
    struct Solution {
      // Note: I renamed s1 to needle and s2 to haystack
      static bool checkInclusion(const string& needle, const string& haystack) {
        if (needle.size() > haystack.size()) { return false; }
        auto window_begin = haystack.begin();
        auto window_end   = window_begin + needle.size();
        auto distance = signed_distance(needle, window_begin);
            
        if (all_zero(distance)) { return true; }
        for (char left, right;;) {
          if (window_end == haystack.end()) { return false; }
          left  = *(window_begin++) - 'a';
          right = *(window_end++) - 'a';
          if (left == right) { continue; }
          --distance[left], ++distance[right];
          if (distance[left] == 0 && distance[right] == 0 && all_zero(distance)) { return true; }
        }
      }
        
    private:
      using CharacterCount = std::array<int, 26>;
    
      static CharacterCount signed_distance(const string& target, const string::const_iterator window){
        CharacterCount counts = CharacterCount{}; // Initializes all elements to zero
        for(size_t i = 0; i < target.size(); ++i) {
          --counts[target[i] - 'a'];
          ++counts[window[i] - 'a'];
        }
        return counts;
      }
        
      static bool all_zero(const CharacterCount& counts) {
        for (auto c : counts) { if (c != 0) { return false; } }
        return true;
      }
    };
    

Log in to reply
 

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