Permutation in String

Decide whether s2 contains some rearrangement of s1 by sliding a window of length s1 over s2 and comparing letter counts.

The idea

Two strings are permutations of each other exactly when they have the same letter counts. A permutation of s1 inside s2 must be a block of exactly m = s1.Length letters, so slide a window of that fixed size along s2. Each step one letter enters on the right and one leaves on the left, so the counts are updated in O(1) instead of being rebuilt.

Code

public static bool CheckInclusion(string s1, string s2) {
    int m = s1.Length;
    if (m > s2.Length) return false;
    var need = new int[26]; var have = new int[26];
    foreach (char c in s1) need[c - 'a']++;
    for (int i = 0; i < s2.Length; i++) {
        have[s2[i] - 'a']++;
        if (i >= m) have[s2[i - m] - 'a']--;
        if (i >= m - 1 && have.AsSpan().SequenceEqual(need)) return true;
    }
    return false;
}

Tips

• Only compare once the window is full (i >= m - 1); a shorter window cannot match.
• Comparing two int[26] arrays costs 26 steps, a constant, so the whole scan is O(n). Keeping a "matches" counter of equal slots avoids even that.
• The same fixed window solves Find All Anagrams in a String: record every start index instead of returning true.

In the .NET library

have.AsSpan().SequenceEqual(need) compares the two arrays element by element without allocating. LINQ's have.SequenceEqual(need) gives the same answer, just slower.