271. Permutation in String

A permutation of s1 is any window in s2 of length len(s1) whose letter frequencies exactly match s1's. Slide a fixed-width window and compare counts.

Key idea

A permutation only rearranges letters, so it has the same multiset of characters. So s2 contains a permutation of s1 exactly when some substring of s2 with length len(s1) has the identical character-frequency table as s1.

Walk-through

1. If len(s1) > len(s2), return false immediately.
2. Build need, the frequency count of s1. Maintain window, the count of the current k = len(s1) characters of s2.
3. Slide the window one character at a time: add the entering character; once the window exceeds size k, remove the leaving character.
4. Whenever window == need, a permutation is found → return true.
5. If the scan ends, return false.

Comparing two fixed-size count tables (26 letters) is O(1), so the whole scan is linear.

Worked example

s1 = "ab", s2 = "eidbaooo", k = 2:

• windows: ei, id, db, ba ← counts {b:1,a:1} == need → true.

Complexity

• Time: O(n) — one pass over s2 with O(1) count comparisons.
• Space: O(1) — at most 26 counts.

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) return false;

        int[] need = new int[26];
        int[] window = new int[26];
        for (int i = 0; i < n; i++) {
            need[s1.charAt(i) - 'a']++;
            window[s2.charAt(i) - 'a']++;
        }
        if (matches(need, window)) return true;

        for (int i = n; i < m; i++) {
            window[s2.charAt(i) - 'a']++;
            window[s2.charAt(i - n) - 'a']--;
            if (matches(need, window)) return true;
        }
        return false;
    }

    private boolean matches(int[] a, int[] b) {
        for (int i = 0; i < 26; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
}