String Permutation Detection: Two Sliding Window Approaches

Given strings s1 and s2, we want to find if any substring of s2 is a permutation of s1.

Solution 1: Fixed Array Sliding - 12ms

The idea: substrings that are permutations of s1 will have the same character count signature. Each slide forward only requires adding the next character’s count and subtracting the first character’s count. We compare signatures after each slide.

Time: O(n) Space: O(1)

bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    if (s1 == s2) return true;
    bool res = false;

    int hash[26] = {0};
    int h[26] = {0};
    int i;
    // Generate hash signature
    for(i=0;i<s1.size();++i) {
        hash[s1[i]-'a']++;
        h[s2[i]-'a']++;
    }

    while(true) {
        res = true;
        // Compare signatures
        for(int j=0;j<26;j++) {
            if (hash[j] != h[j]) {
                res = false;
                break;
            }
        }

        if (res) return true;
        if (i == s2.size()) break;

        // Slide window: remove head, add tail  
        h[s2[i-s1.size()]-'a']--;
        h[s2[i++]-'a']++;
    }

    return false;
}

Optimized Solution: Two Pointers Maintaining Sliding Window - 8ms

Instead of comparing signatures, we transform this into: the sliding window contains characters that can be “consumed” from our target signature. When we can’t consume anymore, we slide as far as needed.

Time: O(n) Space: O(1)

bool checkInclusion(string s1, string s2) {
    int h[26] = {0};
    for(int i=0;i<s1.size();++i) ++h[s1[i]-'a'];
    int win_size = s1.size();

    for(int start=0, end = 0;end<s2.size();++end) {
        if (h[s2[end]-'a'] > 0) --win_size;
        --h[s2[end]-'a'];

        while (win_size==0) {
            // Window matches substring length - found it
            if (end-start+1 == s1.size()) return true;
            // Need to slide forward. Only continue moving end when we find matching characters
            if (++h[s2[start]-'a'] > 0) win_size++;
            start++;
        }
    }
    return false;
}

Proof: Why does end always stay ahead of start?

End moves first, initially consuming the hash values of the target substring. Before start begins sliding, end has already confirmed the target exists somewhere in s2[start...end]. The remaining work is shrinking the range by incrementing start. When the range equals the target substring length, we’ve found our match.

An English explanation:

• i is start, j is end
• Try find a window (i, j) where s2.substr(i, j + 1 - i) contains all chars in s1
• Once found, try reduce window(i, j) such that j + 1 - i == s1.size() while the window still contains all chars in s1 by moving i, return true
• If window no longer contains all chars in s1, keep moving j forward

#sliding-window #two-pointers