Permutation in String

Intuitionwhy a permutation becomes a frequency comparison

The order of characters inside a permutation does not matter. What matters is how many times each lowercase letter appears. For example, ab and ba have different orders but identical counts: one a, one b, and zero of every other letter. Therefore, a substring of s2 is a valid match exactly when its character counts equal the counts of s1.

Every candidate substring must have length s1.length(), so inspect only windows of that fixed size. When the window moves one position right, one character leaves from the left and one character enters on the right. Updating those two counts is enough; rebuilding the entire window would repeat work that the previous window has already done.

Approachone fixed-length window, two count updates

1. 1Return false immediately when s1 is longer than s2, because no substring of s2 can have enough positions to contain a permutation of s1.
2. 2Count each character in s1 in a 26-element array, because lowercase English letters let every character map directly to an index from 0 to 25.
3. 3Build the first window of s2 with length s1.length(), because every possible match must have exactly that many characters.
4. 4Compare the required counts with the first window's counts before sliding, because the initial window is a valid candidate and otherwise it would be skipped.
5. 5For each later position, increment the count of the new rightmost character and decrement the count of the character that leaves on the left, because both windows differ in only those two positions.
6. 6Compare the two arrays after each update and return true on equality, because equal counts are both necessary and sufficient for the current window to be a permutation of s1.
7. 7Return false after every window has been checked, because no unexamined substring remains.

Complexitythe alphabet makes each comparison constant-sized

Annotated solutionC++ · fixed-size sliding window · direct frequency comparison

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        vector<int> required(26, 0);
        vector<int> window(26, 0);

        for (char c : s1) {
            required[c - 'a']++;
        }

        for (int i = 0; i < static_cast<int>(s1.length()); ++i) {
            window[s2[i] - 'a']++;
        }

        if (required == window) {
            return true;
        }

        for (int right = static_cast<int>(s1.length()); right < static_cast<int>(s2.length()); ++right) {
            window[s2[right] - 'a']++;
            window[s2[right - static_cast<int>(s1.length())] - 'a']--;

            if (required == window) {
                return true;
            }
        }

        return false;
    }
};

The subtraction index is the key placement detail. When right is the index of the newly entered character, right - s1.length() is the old left edge of the window. Adding s2[right] before subtracting the outgoing character keeps the current window represented exactly, while the equality check immediately after the update tests that complete window.

The mismatch-count alternativea small constant-factor optimisation, not a different asymptotic bound

Comparing two 26-element vectors is already constant work, but you can avoid even that fixed scan by tracking how many letters currently have the wrong count. Adjust that number whenever an entry changes from equal to unequal or from unequal to equal. This keeps the same O(n) time and O(1) extra space; it only makes each slide do less constant work.

#include <string>
#include <vector>

using namespace std;

class Solution {
    void change(vector<int>& difference, int index, int amount, int& mismatched) {
        if (difference[index] != 0) {
            --mismatched;
        }

        difference[index] += amount;

        if (difference[index] != 0) {
            ++mismatched;
        }
    }

public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        vector<int> difference(26, 0);
        for (char c : s1) {
            ++difference[c - 'a'];
        }

        int mismatched = 0;
        for (int i = 0; i < 26; ++i) {
            if (difference[i] != 0) {
                ++mismatched;
            }
        }

        for (int i = 0; i < static_cast<int>(s1.length()); ++i) {
            change(difference, s2[i] - 'a', -1, mismatched);
        }

        if (mismatched == 0) {
            return true;
        }

        for (int right = static_cast<int>(s1.length()); right < static_cast<int>(s2.length()); ++right) {
            change(difference, s2[right] - 'a', -1, mismatched);
            change(difference, s2[right - static_cast<int>(s1.length())] - 'a', 1, mismatched);

            if (mismatched == 0) {
                return true;
            }
        }

        return false;
    }
};

Here difference stores required count minus current-window count. The helper updates mismatched around each change: it first removes the old status, applies the count change, then adds the new status. This version is an optimisation rather than a new algorithm. The direct vector comparison is often easier to read, while this version is useful when the alphabet is larger or comparisons are no longer tiny.

Common mistakesthe wrong window shape is easy to miss