40. Permutation in String

🔗 LeetCode Problem: 567. Permutation in String
📊 Difficulty: Medium
🏷️ Topics: Hash Table, Two Pointers, String, Sliding Window

Problem Statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints: - 1 <= s1.length, s2.length <= 10^4 - s1 and s2 consist of lowercase English letters.

---

🎨 Visual Understanding

The Problem Visualized

s1 = "ab", s2 = "eidbaooo"

Permutations of "ab": "ab", "ba"

Check all substrings of s2 with length 2:
"ei" → Not a permutation of "ab"
"id" → Not a permutation of "ab"
"db" → Not a permutation of "ab"
"ba" → Permutation of "ab" ✓ Found!

Answer: true

Key Observation: Permutation = Anagram

This problem is essentially:
"Does s2 contain an anagram of s1?"

Permutation and Anagram are the same concept:
- Same characters
- Same frequency
- Different order allowed

s1 = "ab" has permutations: "ab", "ba"
Both are anagrams of each other

Visual Process

s1 = "ab", s2 = "eidbaooo"
s1 frequency: {a:1, b:1}

Slide window of size 2 through s2:

[e i] d b a o o o → {e:1, i:1} ≠ s1 ✗
e [i d] b a o o o → {i:1, d:1} ≠ s1 ✗
e i [d b] a o o o → {d:1, b:1} ≠ s1 ✗
e i d [b a] o o o → {b:1, a:1} = s1 ✓ Match!

Return: true

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all substrings of s2 with length s1.length:
1. For each starting position in s2
2. Extract substring of length s1.length
3. Check if it's a permutation of s1
4. If yes, return true
5. If no substring matches, return false

Why This Works: - Checks all windows - Guaranteed to find if exists - Easy to understand

Why This Fails Requirements: - Time complexity O(n × m) where n = s2.length, m = s1.length - Recounts frequencies for each window - Too slow for large strings - Not optimal for interviews

Implementation

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return false;
    }

    // Get frequency map of s1
    Map<Character, Integer> s1Map = new HashMap<>();
    for (char c : s1.toCharArray()) {
        s1Map.put(c, s1Map.getOrDefault(c, 0) + 1);
    }

    // Check each window
    for (int i = 0; i <= s2.length() - s1.length(); i++) {
        String window = s2.substring(i, i + s1.length());

        if (isPermutation(window, s1Map)) {
            return true;
        }
    }

    return false;
}

private boolean isPermutation(String window, Map<Character, Integer> s1Map) {
    Map<Character, Integer> windowMap = new HashMap<>();
    for (char c : window.toCharArray()) {
        windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
    }
    return windowMap.equals(s1Map);
}

⏰ Time: O(n × m) - n windows, each checked in O(m)
💾 Space: O(m) - for frequency maps

---

✅ Approach 2: Sliding Window with Frequency Array (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use fixed-size sliding window with frequency matching:

This is IDENTICAL to "Find All Anagrams in a String" (LC 438)
But instead of collecting all indices, we return true on first match

Algorithm:
1. Build frequency array for s1
2. Slide window of size s1.length through s2
3. Compare frequencies
4. Return true on first match
5. Return false if no match found

Visual Explanation:

s1 = "ab", s2 = "eidbaooo"

s1 frequency: [a:1, b:1, rest:0]

Window [e i]:
s2 frequency: [e:1, i:1, rest:0]
Match? NO

Window [i d]:
s2 frequency: [i:1, d:1, rest:0]
Match? NO

Window [d b]:
s2 frequency: [d:1, b:1, rest:0]
Match? NO

Window [b a]:
s2 frequency: [a:1, b:1, rest:0]
Match? YES! Return true

Why This Works:

Permutation check = Anagram check
Same algorithm as LC 438 (Find All Anagrams)
But early return on first match instead of collecting all

Implementation (Array Comparison)

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return false;
    }

    // Build frequency arrays
    int[] s1Count = new int[26];
    int[] s2Count = new int[26];

    for (char c : s1.toCharArray()) {
        s1Count[c - 'a']++;
    }

    // Build first window
    for (int i = 0; i < s1.length(); i++) {
        s2Count[s2.charAt(i) - 'a']++;
    }

    // Check first window
    if (Arrays.equals(s1Count, s2Count)) {
        return true;
    }

    // Slide window through s2
    for (int i = s1.length(); i < s2.length(); i++) {
        // Add right character
        s2Count[s2.charAt(i) - 'a']++;

        // Remove left character
        s2Count[s2.charAt(i - s1.length()) - 'a']--;

        // Check current window
        if (Arrays.equals(s1Count, s2Count)) {
            return true;
        }
    }

    return false;
}

⏰ Time: O(n × 26) = O(n) - n windows, each compared in O(26)
💾 Space: O(1) - arrays of fixed size 26

---

✅ Approach 3: Sliding Window with Counter (Most Optimal)

The Further Optimization 💡

Core Logic:

Use matches counter for O(1) comparison:

matches = number of characters with matching frequency
If matches == 26, we have a permutation

Early return on first match

Implementation (With Counter)

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return false;
    }

    // Build frequency arrays
    int[] s1Count = new int[26];
    int[] s2Count = new int[26];

    for (char c : s1.toCharArray()) {
        s1Count[c - 'a']++;
    }

    // Build first window and count matches
    for (int i = 0; i < s1.length(); i++) {
        s2Count[s2.charAt(i) - 'a']++;
    }

    // Count initial matches
    int matches = 0;
    for (int i = 0; i < 26; i++) {
        if (s1Count[i] == s2Count[i]) {
            matches++;
        }
    }

    // Check first window
    if (matches == 26) {
        return true;
    }

    // Slide window
    for (int i = s1.length(); i < s2.length(); i++) {
        // Add right character
        int rightIdx = s2.charAt(i) - 'a';
        s2Count[rightIdx]++;
        if (s2Count[rightIdx] == s1Count[rightIdx]) {
            matches++;
        } else if (s2Count[rightIdx] == s1Count[rightIdx] + 1) {
            matches--;
        }

        // Remove left character
        int leftIdx = s2.charAt(i - s1.length()) - 'a';
        s2Count[leftIdx]--;
        if (s2Count[leftIdx] == s1Count[leftIdx]) {
            matches++;
        } else if (s2Count[leftIdx] == s1Count[leftIdx] - 1) {
            matches--;
        }

        // Check if permutation found
        if (matches == 26) {
            return true;
        }
    }

    return false;
}

⏰ Time: O(n) - single pass, O(1) comparison per window
💾 Space: O(1) - arrays of fixed size 26

---

🔍 Step-by-Step Execution

Example: s1 = "ab", s2 = "eidbaooo"

Initial State:
═══════════════════════════════════════════════════════════════════
s1 = "ab"
s2 = "eidbaooo"

s1Count = [a:1, b:1, rest:0]
s2Count = [all 0]


Step 1: Build first window [e i]
═══════════════════════════════════════════════════════════════════
Add s2[0]='e': s2Count[e]=1
Add s2[1]='i': s2Count[i]=1

s2Count = [e:1, i:1, rest:0]

Compare: s1Count == s2Count? NO ✗
(s1Count has a:1,b:1 but s2Count has e:1,i:1)


Step 2: Slide window to position 1 [i d]
═══════════════════════════════════════════════════════════════════
Remove s2[0]='e': s2Count[e]=0
Add s2[2]='d': s2Count[d]=1

s2Count = [d:1, i:1, rest:0]

Compare: s1Count == s2Count? NO ✗


Step 3: Slide window to position 2 [d b]
═══════════════════════════════════════════════════════════════════
Remove s2[1]='i': s2Count[i]=0
Add s2[3]='b': s2Count[b]=1

s2Count = [b:1, d:1, rest:0]

Compare: s1Count == s2Count? NO ✗


Step 4: Slide window to position 3 [b a]
═══════════════════════════════════════════════════════════════════
Remove s2[2]='d': s2Count[d]=0
Add s2[4]='a': s2Count[a]=1

s2Count = [a:1, b:1, rest:0]

Compare: s1Count == s2Count? YES ✓

Return: true


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: true
═══════════════════════════════════════════════════════════════════

Example 2: s1 = "ab", s2 = "eidboaoo"

Check all windows of size 2:

[e i] → {e:1, i:1} ≠ s1 ✗
[i d] → {i:1, d:1} ≠ s1 ✗
[d b] → {d:1, b:1} ≠ s1 ✗
[b o] → {b:1, o:1} ≠ s1 ✗
[o a] → {o:1, a:1} ≠ s1 ✗
[a o] → {a:1, o:1} ≠ s1 ✗
[o o] → {o:2} ≠ s1 ✗

No match found
Return: false

---

🔍 Edge Cases

Case 1: s1 longer than s2
Input: s1 = "abc", s2 = "ab"
Output: false
Explanation: No substring of length 3 in s2

Case 2: Exact match
Input: s1 = "ab", s2 = "ab"
Output: true

Case 3: Permutation at start
Input: s1 = "ab", s2 = "baooo"
Output: true

Case 4: Permutation at end
Input: s1 = "ab", s2 = "oooab"
Output: true

Case 5: Multiple permutations
Input: s1 = "ab", s2 = "ababab"
Output: true
Explanation: First window "ab" is already a match

Case 6: No permutation
Input: s1 = "ab", s2 = "cdefgh"
Output: false

Case 7: Single character
Input: s1 = "a", s2 = "abc"
Output: true

Case 8: All same characters
Input: s1 = "aa", s2 = "aaaa"
Output: true

---

Common Mistakes

Mistake 1: Not checking s1.length > s2.length
❌ Wrong: 
    // No check, may cause issues
✓ Right: 
    if (s1.length() > s2.length()) return false;
Reason: Cannot have substring longer than string

Mistake 2: Wrong window slide indices
❌ Wrong: 
    for (int i = 0; i < s2.length(); i++) {
        // Add s2[i + s1.length()] - out of bounds!
    }
✓ Right: 
    for (int i = s1.length(); i < s2.length(); i++) {
        // Add s2[i], remove s2[i - s1.length()]
    }
Reason: Must ensure indices are valid

Mistake 3: Using == for array comparison
❌ Wrong: 
    if (s1Count == s2Count) {  // Compares references, not content
        return true;
    }
✓ Right: 
    if (Arrays.equals(s1Count, s2Count)) {
        return true;
    }
Reason: Arrays need Arrays.equals()

Mistake 4: Not checking first window
❌ Wrong: 
    // Start loop from s1.length() without checking first window
✓ Right: 
    // Check first window before sliding
    if (Arrays.equals(s1Count, s2Count)) {
        return true;
    }
Reason: First window not checked in loop

Mistake 5: Continuing after finding match
❌ Wrong: 
    if (Arrays.equals(s1Count, s2Count)) {
        found = true;  // But continue looping
    }
✓ Right: 
    if (Arrays.equals(s1Count, s2Count)) {
        return true;  // Early return
    }
Reason: Can return immediately on first match

Mistake 6: Wrong matches counter update
❌ Wrong: 
    if (s2Count[rightIdx] == s1Count[rightIdx]) {
        matches++;  // Always increment
    }
✓ Right: 
    if (s2Count[rightIdx] == s1Count[rightIdx]) {
        matches++;
    } else if (s2Count[rightIdx] == s1Count[rightIdx] + 1) {
        matches--;  // Was matching, now not
    }
Reason: Need to handle both match and unmatch cases

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n × m)
  Space: O(m)
  Use: Only for understanding

Approach 2: Sliding Window + Array Comparison
  Time: O(n × 26) = O(n)
  Space: O(1)
  Use: Simple and effective

Approach 3: Sliding Window + Counter (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Most optimal, best for interviews

🔑 The Core Insight

Permutation Detection = Anagram Detection:

This problem is essentially:
"Does s2 contain an anagram of s1?"

Same Algorithm as LC 438 (Find All Anagrams):
- Fixed-size sliding window (size = s1.length)
- Frequency array comparison
- Check if current window is permutation/anagram

Key Difference:
LC 438: Return list of ALL matching indices
LC 567: Return true on FIRST match (early return)

Permutation Properties:
1. Same length (guaranteed by fixed window)
2. Same characters
3. Same character frequencies
4. Different order is allowed

Template:
1. Build frequency for s1
2. Build frequency for first window
3. Check first window → return true if match
4. For remaining positions:
   - Slide window (remove left, add right)
   - Check frequencies → return true if match
5. Return false if no match found

🎯 Pattern Recognition

Problem Type: Permutation Detection in String
Core Pattern: Fixed-Size Sliding Window + Frequency Matching

When to Apply:
✓ Finding permutation/anagram in string
✓ Fixed window size (pattern length)
✓ Character frequency matching
✓ Boolean result (contains or not)
✓ Want O(n) time complexity

Key Techniques:
→ Fixed-size sliding window
→ Frequency array (size 26 for lowercase)
→ Incremental frequency updates
→ Early return on first match
→ Array comparison or counter method

Relationship to Other Problems:
- LC 438 (Find All Anagrams): Same algorithm, collect all indices
- LC 567 (Permutation in String): Same algorithm, return on first match
- Both use identical sliding window + frequency matching

Related Problems:
- Find All Anagrams in a String (LC 438)
- Minimum Window Substring (LC 76)
- Substring with Concatenation of All Words (LC 30)

🧠 Interview Strategy

Step 1: "Need to check if s2 contains permutation of s1"
Step 2: "Permutation = anagram = same character frequencies"
Step 3: "Fixed window size = s1.length"
Step 4: "Slide window, compare frequencies"
Step 5: "Early return true on first match"
Step 6: "O(n) time with frequency arrays"

Key Points to Mention:
- Permutation is same as anagram
- Fixed-size sliding window
- Frequency array for counting
- Slide: remove left, add right
- Arrays.equals() or counter for comparison
- Early return on first match (optimization)
- Same as Find All Anagrams but boolean result
- O(n) time, O(1) space

---

📝 Quick Revision Notes

🎯 Core Concept:

Permutation detection = anagram detection. Use fixed-size sliding window (size = s1.length) with frequency arrays. Early return on first match.

⚡ Quick Implementation (Array Comparison):

class Test {
  public boolean checkInclusion(String s1, String s2) {
    final int len1 = s1.length();
    final int len2 = s2.length();

    if (len1 > len2) {
      return false;
    }

    int[] s1Count = new int[26];
    int[] s2Count = new int[26];

    // // Approach 1
    // // freq map of s1 till s1 length
    // for (int i = 0; i < len1; i++) {
    // s1Count[s1.charAt(i) - 'a']++;
    // }

    // // freq map of s2 till s1 length itself (not s2)
    // for (int i = 0; i < len1; i++) {
    // s2Count[s2.charAt(i) - 'a']++;
    // }

    // if (Arrays.equals(s1Count, s2Count)) {
    // return true;
    // }

    // for (int i = len1; i < len2; i++) {
    // s2Count[s2.charAt(i - len1) - 'a']--;
    // s2Count[s2.charAt(i) - 'a']++;

    // if (Arrays.equals(s1Count, s2Count)) {
    // return true;
    // }
    // }

    // Approach 2
    for (int i = 0; i < len1; i++) {
      s1Count[s1.charAt(i) - 'a']++;
    }

    for (int i = 0; i < len1; i++) {
      s2Count[s2.charAt(i) - 'a']++;
    }

    int matches = 0;
    for (int i = 0; i < 26; i++) {
      if (s1Count[i] == s2Count[i]) {
        matches++;
      }
    }

    if (matches == 26) {
      return true;
    }

    for (int i = len1; i < len2; i++) {
      // shrink
      int leftIndex = s2.charAt(i - len1) - 'a';
      if (s2Count[leftIndex] == s1Count[leftIndex]) {
        matches--;
      }
      s2Count[leftIndex]--;
      if (s2Count[leftIndex] == s1Count[leftIndex]) {
        matches++;
      }

      // expand
      int rightIndex = s2.charAt(i) - 'a';
      if (s2Count[rightIndex] == s1Count[rightIndex]) {
        matches--;
      }
      s2Count[rightIndex]++;
      if (s2Count[rightIndex] == s1Count[rightIndex]) {
        matches++;
      }

      if (matches == 26) {
        return true;
      }
    }

    return false;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.checkInclusion("ab", "eidbaooo"));
    System.out.println(t.checkInclusion("ab", "eidboaoo"));
  }
}

🔑 Key Insights:

• Permutation = Anagram: Same character frequencies
• Fixed window: Size = s1.length (constant)
• Early return: Return true on first match
• Same as LC 438: But return boolean instead of collecting indices
• Frequency arrays: Size 26 for lowercase letters
• Incremental update: Remove left, add right (O(1))
• Comparison: Arrays.equals() takes O(26) = O(1)
• First window: Check before loop starts
• Counter optimization: Track matches for O(1) comparison
• Time: O(n) - single pass with constant work per position
• Space: O(1) - fixed-size arrays

🎪 Memory Aid:

"Permutation = Anagram! Fixed window, frequency match, EARLY RETURN!"
Think: "Same as Find All Anagrams, but stop at FIRST match"

---

Related Patterns

• Find All Anagrams in a String (LC 438)
• Minimum Window Substring (LC 76)
• Longest Substring Without Repeating Characters (LC 3)
• Substring with Concatenation of All Words (LC 30)

---

Happy practicing! 🎯