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

• 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;
}
};
``````

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