Sliding WindowHardO(n + m) time · O(1) space

Permutation in a String

Mahabharata — Vyasa's Secret Cipher — The Anagram Hidden in the Scroll of Kings

अक्षरैः समस्तैः यत्र सम्भवति तत् क्षणे। खिड़कीं सार्थकां वित्त — परिवर्तन-युक्ता सा॥

*When all the required letters appear in a window — know that window to be meaningful. It is a permutation in disguise.*

The Story

Sage Vyasa was composing a secret message for the Pandavas during their incognito exile (Ajnatavasa). He embedded the message as an anagram within the royal proclamations scroll. The Pandavas would know to look for any window in the main scroll `s2` of the same length as the key word `s1`, where the characters were a permutation (rearrangement) of `s1`.

"Does the string `s1 = 'ab'` appear as a permutation anywhere in `s2 = 'eidbaooo'`?"

Arjuna, sharpest of the brothers, examined the scroll: - Window [0..1] = "ei" — not a permutation of "ab" - Window [1..2] = "id" — no - Window [2..3] = "db" — no - Window [3..4] = "ba" — YES! "ba" is a permutation of "ab"!

"The answer is true," Arjuna confirmed.

"But for a long scroll with millions of characters," Yudhishthira pressed, "we cannot check every window manually."

The algorithm was clear: a FIXED window of size `s1.length()`. As we slide this window across `s2`, we must check if the current window's character frequencies exactly match `s1`'s frequencies.

Nakula, the careful thinker, proposed the efficient approach:

"Build a frequency array `freq` of size 26 for `s1`. As we initialize the first window of `s2`, SUBTRACT each character's frequency. If a character in `s2`'s window matches one in `s1`, its count goes down. If all 26 counts are zero, the window is a permutation."

"But checking all 26 positions each time is O(26) per slide — still O(26n) = O(n). Can we do better?"

"Yes," Nakula said. "Track a `matches` counter — the number of positions in `freq` that are currently 0. When a freq cell goes to 0, increment `matches`. When it goes away from 0, decrement `matches`. When `matches == 26`, all frequencies are balanced: the window is a permutation."

Sahadeva demonstrated with `s1="ab"`, `s2="eidbaooo"`:

freq initialized: freq['a'-'a']=1, freq['b'-'a']=1, all others=0. matches = 24 (26 - 2 non-zero positions).

First window [0..1] = "ei": - 'e': freq['e'-'a']=0 → -1 (now -1, was 0, so matches--=23) - 'i': freq['i'-'a']=0 → -1 (matches--=22) matches=22 ≠ 26. Not a permutation.

Slide right=2 ('d'): add 'd', remove 'e': - Add 'd': freq['d'-'a']=0→-1, matches--=21 - Remove 'e': freq['e'-'a']=-1→0, matches++=22 matches=22 ≠ 26.

Slide right=3 ('b'): add 'b', remove 'i': - Add 'b': freq['b'-'a']=1→0, matches++=23 - Remove 'i': freq['i'-'a']=-1→0, matches++=24 matches=24 ≠ 26.

Slide right=4 ('a'): add 'a', remove 'd': - Add 'a': freq['a'-'a']=1→0, matches++=25 - Remove 'd': freq['d'-'a']=-1→0, matches++=26 matches=26! Return true!

"The window [3..4] = 'ba' is a permutation of 'ab'," Sahadeva confirmed.

Yudhishthira found the hidden message in the proclamation scroll. The Pandavas survived their incognito year, guided by Vyasa's cleverly embedded anagram.

"Remember," Nakula said, "the `matches` counter transforms the O(26) equality check into O(1) per slide. This is the fixed-window frequency-matching technique — the purest form of the sliding window."

This is the fixed Sliding Window with frequency matching for permutation detection.

Arjuna's First Instinct

For every window of size s1.length(), sort the window characters and compare to sorted s1. Or compare frequency arrays. O(n × m) time.

java

public boolean checkInclusionBruteForce(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    
    int[] need = new int[26];
    for (char c : s1.toCharArray()) need[c - 'a']++;
    
    for (int i = 0; i <= s2.length() - s1.length(); i++) {
        int[] have = new int[26];
        for (int j = i; j < i + s1.length(); j++) {
            have[s2.charAt(j) - 'a']++;
        }
        if (Arrays.equals(need, have)) return true;  // O(26) comparison
    }
    return false;
}

Nakula's Wisdom

Nakula's insight: build a single `freq` array as the difference between s1 requirements and s2 window. Track `matches` — positions where freq[i]==0. When matches==26, the window is a permutation. Sliding is O(1): update two positions (add right, remove left), adjust matches accordingly.

java

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    
    int[] freq = new int[26];
    int matches = 0;
    
    // Initialize freq with s1 requirements
    for (char c : s1.toCharArray()) freq[c - 'a']++;
    
    // Count how many positions start at 0 (already 'matched')
    for (int i = 0; i < 26; i++) {
        if (freq[i] == 0) matches++;
    }
    
    // Initialize first window in s2
    for (int i = 0; i < s1.length(); i++) {
        int c = s2.charAt(i) - 'a';
        if (freq[c] == 1) matches++;   // Going to 0: now matched
        else if (freq[c] == 0) matches--;  // Going away from 0: no longer matched
        freq[c]--;
    }
    
    if (matches == 26) return true;
    
    // Slide the window
    for (int i = s1.length(); i < s2.length(); i++) {
        // Add new right character
        int right = s2.charAt(i) - 'a';
        if (freq[right] == 1) matches++;
        else if (freq[right] == 0) matches--;
        freq[right]--;
        
        // Remove old left character  
        int left = s2.charAt(i - s1.length()) - 'a';
        if (freq[left] == -1) matches++;  // Going back to 0: now matched
        else if (freq[left] == 0) matches--;  // Going away from 0 again
        freq[left]++;
        
        if (matches == 26) return true;
    }
    
    return false;
}

// Simpler alternative using 'formed' count
public boolean checkInclusionSimple(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']--;
    if (allZero(freq)) return true;
    for (int i = s1.length(); i < s2.length(); i++) {
        freq[s2.charAt(i) - 'a']--;               // Add right
        freq[s2.charAt(i - s1.length()) - 'a']++;  // Remove left
        if (allZero(freq)) return true;
    }
    return false;
}

private boolean allZero(int[] arr) {
    for (int v : arr) if (v != 0) return false;
    return true;
}

Step-by-Step Walkthrough

s1 = "abc",  s2 = "bbbca"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Init freq from s1="abc": freq={a:1, b:1, c:1}

First window s2[0..2]="bbb":
  freq[b]=1→0, freq[b]=0→-1, freq[b]=-1→-2
  freq = {a:1, b:-2, c:1}
  allZero? No

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Slide i=3 (add 'c', remove s2[0]='b'):
  freq[c]=1→0
  freq[b]=-2→-1
  freq={a:1, b:-1, c:0} → not all zero

Slide i=4 (add 'a', remove s2[1]='b'):
  freq[a]=1→0
  freq[b]=-1→0
  freq={a:0, b:0, c:0} → ALL ZERO!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return true  (s2[2..4]="bca" is a permutation of "abc")

Deep Insight

**The freq difference approach:** `freq[i] = count_in_s1[i] - count_in_current_window[i]` - freq[i] > 0: we still need more of character i - freq[i] < 0: we have too many of character i - freq[i] = 0: character i is perfectly balanced All 26 zeros → perfect match → permutation found.

**The matches counter optimization:** Checking `allZero()` is O(26) per slide. The `matches` counter reduces this to O(1). We maintain `matches` = number of i where freq[i]==0. When matches==26, all zeros.

**Fixed vs variable window:** This is a FIXED window problem (size = s1.length). We don't need to shrink — we slide exactly one step at a time (add one right, remove one left).

**Connection to sw-11 (String Anagrams):** sw-10 asks "does a permutation exist?" (return boolean) sw-11 asks "find all permutation start indices" (return list) Same algorithm, different return value.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n × m)	O(1)	n windows, O(m) or O(26) per window comparison
Optimal	O(n + m)	O(1)	O(m) init + O(n) sliding; freq array is O(26)=O(1)

Pattern Recognition

✅ Fixed window of size s1.length()
✅ Check if window is a permutation of s1
✅ Frequency difference array: all-zero means permutation
✅ O(1) slide using matches counter or allZero check

**LeetCode Trigger Phrases:**
→ "permutation of s1... in s2"
→ "check if any window is an anagram"
→ "character frequency" + "fixed window size"

Bhagavad Gita 2.41

व्यवसायात्मिका बुद्धिरेकेह कुरुनन्दन। बहुशाखा ह्यनन्ताश्च बुद्धयोऽव्यवसायिनाम्॥

Those who are on this path are resolute in purpose, and their aim is one. O beloved child of the Kurus, the intelligence of those who are irresolute is many-branched and endless.

Connection: The permutation check requires exactly the right characters in exactly the right counts — any excess or deficiency fails the test. Like the resolute intelligence the Gita describes (single-pointed, not scattered), the algorithm maintains a single-purpose freq array and a single matches counter. The scattered approach (brute force, checking all branches) fails at scale; the focused approach (track the difference, check one number) succeeds in O(n).