Problem Statement

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

A permutation of a string is a rearrangement of its letters. For example, "ab" has permutations "ab" and "ba".

Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: "ba" is a permutation of "ab" and is a substring of s2.

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.

---

Approach in Plain English

1. We want to check if any substring of s2 has the same characters as s1 (order doesn’t matter).
2. Use sliding window of size s1.length() on s2.
3. Maintain two arrays of size 26 (for lowercase letters):
   • s1Count → frequency of letters in s1.
   • windowCount → frequency of letters in current window of s2.
4. Slide the window through s2:
   • Add new character (right end) to windowCount.
   • Remove character leaving the window (left end) from windowCount.
   • Compare windowCount and s1Count. If equal → permutation found → return true.
5. If no match is found after sliding through s2, return false.

Key idea: By comparing counts instead of sorting, we reduce time complexity to O(n).

---

Beginner-Friendly Dry Run

Take s1 = "ab" and s2 = "eidbaooo".

1. s1.length = 2 → window size = 2.
2. Frequency count of s1: a=1, b=1.
3. Slide window over s2:
   • Window "ei" (indices 0-1):
     • windowCount: e=1, i=1
     • Compare with s1Count: not equal → continue.
   • Window "id" (indices 1-2):
     • windowCount: i=1, d=1 → not equal.
   • Window "db" (indices 2-3):
     • windowCount: d=1, b=1 → not equal.
   • Window "ba" (indices 3-4):
     • windowCount: b=1, a=1 → matches s1Count → return true.
4. Result → true.

---

Textual Approach

• Count letters in s1.
• Initialize a sliding window on s2 of length equal to s1.
• Update window count dynamically as window moves:
  • Add rightmost character.
  • Remove leftmost character.
• Compare counts → if equal, permutation exists.

---

Java Code

import java.util.Arrays;

public class PermutationInString {

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

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

        for (char c : s1.toCharArray()) {
            s1Count++;
        }

        int windowSize = s1.length();

        for (int i = 0; i < s2.length(); i++) {
            // Add current character to window
            windowCount[s2.charAt(i) - 'a']++;

            // Remove leftmost character if window exceeded size
            if (i >= windowSize) {
                windowCount[s2.charAt(i - windowSize) - 'a']--;
            }

            // Compare arrays for match
            if (Arrays.equals(s1Count, windowCount)) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = "eidbaooo";
        System.out.println(checkInclusion(s1, s2)); // Output: true

        String s3 = "ab";
        String s4 = "eidboaoo";
        System.out.println(checkInclusion(s3, s4)); // Output: false
    }
}

---

Key Points

• Sliding window technique ensures O(n) time complexity.
• Use frequency arrays of size 26 for lowercase letters.
• Always remove the character leaving the window and add the new one.
• Compare frequency arrays to detect permutations efficiently.