Permutation in String [Medium] — Fixed Window Character Count

Problem Statement

Return true if one of s1's permutations is a substring of s2.

Input: s1="ab", s2="eidbaooo" → true ("ba" at index 3)
Input: s1="ab", s2="eidboaoo" → false

Intuition

A permutation of s1 is any arrangement of its characters, so we need a window of size len(s1) in s2 where the character frequencies match s1's. Use a fixed window that slides one character at a time.

Solutions

C++

bool checkInclusion(string s1, string s2) {
    if(s1.size()>s2.size()) return false;
    int freq[26]={};
    for(char c:s1) freq[c-'a']++;
    for(char c:s2.substr(0,s1.size())) freq[c-'a']--;
    auto check=[&](){for(int x:freq) if(x) return false; return true;};
    if(check()) return true;
    for(int i=s1.size();i<s2.size();i++){
        freq[s2[i]-'a']--;
        freq[s2[i-s1.size()]-'a']++;
        if(check()) return true;
    }
    return false;
}

Java

public boolean checkInclusion(String s1, String s2) {
    if(s1.length()>s2.length()) return false;
    int[] freq=new int[26];
    for(char c:s1.toCharArray()) freq[c-'a']++;
    for(int i=0;i<s1.length();i++) freq[s2.charAt(i)-'a']--;
    int matches=0; for(int x:freq) if(x==0) matches++;
    for(int i=s1.length();i<s2.length();i++){
        int in=s2.charAt(i)-'a', out=s2.charAt(i-s1.length())-'a';
        if(--freq[in]==0) matches++; else if(freq[in]==-1) matches--;
        if(++freq[out]==0) matches++; else if(freq[out]==1) matches--;
        if(matches==26) return true;
    }
    return false;
}

Python

from collections import Counter

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    k = len(s1)
    need = Counter(s1)
    window = Counter(s2[:k])
    if need == window: return True
    for i in range(k, len(s2)):
        window[s2[i]] += 1
        left = s2[i-k]
        window[left] -= 1
        if window[left] == 0: del window[left]
        if window == need: return True
    return False

JavaScript

var checkInclusion = function(s1, s2) {
    if(s1.length>s2.length) return false;
    const freq=new Array(26).fill(0);
    for(const c of s1) freq[c.charCodeAt(0)-97]++;
    for(let i=0;i<s1.length;i++) freq[s2.charCodeAt(i)-97]--;
    let matches=freq.filter(x=>x===0).length;
    for(let i=s1.length;i<s2.length;i++){
        const in_=s2.charCodeAt(i)-97, out=s2.charCodeAt(i-s1.length)-97;
        if(--freq[in_]===0)matches++;else if(freq[in_]===-1)matches--;
        if(++freq[out]===0)matches++;else if(freq[out]===1)matches--;
        if(matches===26) return true;
    }
    return false;
};

Complexity

Time: O(|s1| + |s2|)
Space: O(1) — 26-char alphabet