To solve this via brute force, we iterate through every possible substring of s2 that has the same length as s1. For each substring, we sort its characters and compare the result to the sorted version of s1.

Pseudo-code:

text
n = length of s1
sorted_s1 = sort(s1)

for i from 0 to length of s2 - n:
    substring = s2[i : i + n]
    sorted_substring = sort(substring)
    if sorted_substring == sorted_s1:
        return true

return false

Time Complexity: $O((L_2 - L_1) \cdot L_1 \log L_1)$, where $L_1$ is the length of s1 and $L_2$ is the length of s2. The sorting operation inside the loop drives the complexity. Why it fails: While correct, this approach is inefficient. With string lengths up to $10^4$, the sorting operation inside the loop creates a bottleneck, potentially leading to a Time Limit Exceeded (TLE) error on large test cases. We need a linear time solution.

Core Insight for Permutation in String

The transition from brute force to the optimal solution relies on avoiding the repeated work of sorting or re-counting characters for every new substring.

We know that s1 has a fixed set of character frequencies (e.g., "aab" is {a:2, b:1}). As we slide a window of length len(s1) across s2, only two characters change at each step:

1. The character leaving the window (at the left).
2. The character entering the window (at the right).

Instead of recounting the entire window, we can maintain a running frequency map. We decrement the count of the character leaving the window and increment the count of the character entering it. At any point, if the frequency map of the current window matches the frequency map of s1, we have found a valid permutation.

Visual Description: Imagine two frequency arrays of size 26 (representing 'a' through 'z'). One array stores the static counts for s1. The second array represents the dynamic counts of the current window in s2. As the index advances, the algorithm updates the dynamic array at two specific indices—incrementing the new character's index and decrementing the old one—and then compares the two arrays for equality.

Execution Flow

Let s1 = "ab" and s2 = "eidbaooo". Length of s1 is 2.

1. Setup:

   • s1_counts: {'a': 1, 'b': 1} (others 0).
   • Initialize window_counts with first 2 chars of s2 ("ei"): {'e': 1, 'i': 1}.
   • Compare: No match.

2. Slide 1 (Index 2, char 'd'):

   • Enter 'd', Remove 'e'.
   • window_counts: {'i': 1, 'd': 1}.
   • Compare: No match.

3. Slide 2 (Index 3, char 'b'):

   • Enter 'b', Remove 'i'.
   • window_counts: {'d': 1, 'b': 1}.
   • Compare: No match.

4. Slide 3 (Index 4, char 'a'):

   • Enter 'a', Remove 'd'.
   • window_counts: {'b': 1, 'a': 1}.
   • Compare: Match found! Return true.

Proof of Correctness

The algorithm relies on the fundamental property of permutations: two strings are permutations if and only if they have identical character frequency maps. The sliding window ensures we check every contiguous substring of length len(s1) in s2. By maintaining the invariant that window_counts always reflects the current substring's composition, the comparison step correctly identifies if a permutation exists. Since we traverse s2 exhaustively, no potential matches are skipped.

Reference Implementation

C++ Solution for LeetCode 567

cpp
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        vector<int> s1_map(26, 0);
        vector<int> s2_map(26, 0);
        int window_size = s1.length();

        // Initialize the frequency maps for s1 and the first window of s2
        for (int i = 0; i < window_size; i++) {
            s1_map[s1[i] - 'a']++;
            s2_map[s2[i] - 'a']++;
        }

        // Check the first window
        if (s1_map == s2_map) return true;

        // Slide the window across s2
        for (int i = window_size; i < s2.length(); i++) {
            // Add new character to the window
            s2_map[s2[i] - 'a']++;
            // Remove the character leaving the window
            s2_map[s2[i - window_size] - 'a']--;

            // Check if current window matches
            if (s1_map == s2_map) return true;
        }

        return false;
    }
};

Java Solution for LeetCode 567

java
import java.util.Arrays;

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

        int[] s1Map = new int[26];
        int[] s2Map = new int[26];
        int windowSize = s1.length();

        // Initialize frequency maps
        for (int i = 0; i < windowSize; i++) {
            s1Map[s1.charAt(i) - 'a']++;
            s2Map[s2.charAt(i) - 'a']++;
        }

        // Check initial window
        if (Arrays.equals(s1Map, s2Map)) return true;

        // Slide window
        for (int i = windowSize; i < s2.length(); i++) {
            // Add new character
            s2Map[s2.charAt(i) - 'a']++;
            // Remove old character
            s2Map[s2.charAt(i - windowSize) - 'a']--;

            // Compare maps
            if (Arrays.equals(s1Map, s2Map)) return true;
        }

        return false;
    }
}

Python Solution for LeetCode 567

python
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
            
        s1_map = [0] * 26
        s2_map = [0] * 26
        
        # Initialize frequency maps
        for i in range(len(s1)):
            s1_map[ord(s1[i]) - ord('a')] += 1
            s2_map[ord(s2[i]) - ord('a')] += 1
            
        # Check initial window
        if s1_map == s2_map:
            return True
            
        # Slide window
        for i in range(len(s1), len(s2)):
            # Add new character
            s2_map[ord(s2[i]) - ord('a')] += 1
            # Remove old character
            s2_map[ord(s2[i - len(s1)]) - ord('a')] -= 1
            
            if s1_map == s2_map:
                return True
                
        return False