# Permutation in String

- **Canonical ID**: `permutation-in-string`
- **Canonical URL**: https://dsacheatsheet.com/problems/permutation-in-string
- **Difficulty**: medium
- **Patterns**: Sliding Window
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/permutation-in-string/

## 1. Core Invariant / The Trick

Maintain a fixed window of size `len(s1)` sliding over `s2`, updating character match count `matches` out of 26 in O(1) per slide instead of comparing two 26-arrays every step.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Pre-computes initial window, then performs O(1) incremental adjustment for incoming and outgoing char.

## 3. Minimal Idiomatic Code

### Python
```python
def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    c1, c2 = [0] * 26, [0] * 26
    for i in range(len(s1)):
        c1[ord(s1[i]) - 97] += 1
        c2[ord(s2[i]) - 97] += 1
    matches = sum(1 for i in range(26) if c1[i] == c2[i])
    for r in range(len(s1), len(s2)):
        if matches == 26: return True
        idx_in = ord(s2[r]) - 97
        c2[idx_in] += 1
        if c2[idx_in] == c1[idx_in]: matches += 1
        elif c2[idx_in] - 1 == c1[idx_in]: matches -= 1
        idx_out = ord(s2[r - len(s1)]) - 97
        c2[idx_out] -= 1
        if c2[idx_out] == c1[idx_out]: matches += 1
        elif c2[idx_out] + 1 == c1[idx_out]: matches -= 1
    return matches == 26
```

### TypeScript
```typescript
export function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;
  const c1 = new Int32Array(26), c2 = new Int32Array(26);
  for (let i = 0; i < s1.length; i++) {
    c1[s1.charCodeAt(i) - 97]++;
    c2[s2.charCodeAt(i) - 97]++;
  }
  let matches = 0;
  for (let i = 0; i < 26; i++) if (c1[i] === c2[i]) matches++;
  for (let r = s1.length; r < s2.length; r++) {
    if (matches === 26) return true;
    const inIdx = s2.charCodeAt(r) - 97;
    c2[inIdx]++;
    if (c2[inIdx] === c1[inIdx]) matches++;
    else if (c2[inIdx] - 1 === c1[inIdx]) matches--;
    const outIdx = s2.charCodeAt(r - s1.length) - 97;
    c2[outIdx]--;
    if (c2[outIdx] === c1[outIdx]) matches++;
    else if (c2[outIdx] + 1 === c1[outIdx]) matches--;
  }
  return matches === 26;
}
```

### C++
```cpp
bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;
    vector<int> c1(26), c2(26);
    for (size_t i = 0; i < s1.size(); ++i) { c1[s1[i]-'a']++; c2[s2[i]-'a']++; }
    if (c1 == c2) return true;
    for (size_t i = s1.size(); i < s2.size(); ++i) {
        c2[s2[i]-'a']++; c2[s2[i-s1.size()]-'a']--;
        if (c1 == c2) return true;
    }
    return false;
}
```

### Java
```java
boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    int[] c1 = new int[26], c2 = new int[26];
    for (int i = 0; i < s1.length(); i++) { c1[s1.charAt(i)-'a']++; c2[s2.charAt(i)-'a']++; }
    if (Arrays.equals(c1, c2)) return true;
    for (int i = s1.length(); i < s2.length(); i++) {
        c2[s2.charAt(i)-'a']++; c2[s2.charAt(i-s1.length())-'a']--;
        if (Arrays.equals(c1, c2)) return true;
    }
    return false;
}
```

### Go
```go
func checkInclusion(s1, s2 string) bool {
    if len(s1) > len(s2) { return false }
    var c1, c2 [26]int
    for i := range s1 { c1[s1[i]-'a']++; c2[s2[i]-'a']++ }
    if c1 == c2 { return true }
    for i := len(s1); i < len(s2); i++ {
        c2[s2[i]-'a']++; c2[s2[i-len(s1)]-'a']--
        if c1 == c2 { return true }
    }
    return false
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Guarding `len(s1) > len(s2)` immediately prevents index bounds errors.

### Follow-ups
- Find All Anagrams in a String records every index where `matches == 26`.