Data Structures & Algorithms (Sliding Window): Permutation in String

February 4, 2026

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

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

Playground: Leetcode 567

Key Observations

All permutations of a string have the same character frequencies.

Therefore, if the frequency map of any substring of s2 having length s1.length() matches the frequency map of s1, then that substring is a valid permutation of s1, and s2 contains a permutation of s1.

Naive Approach - Nested Loops

Iterate over every substring of s2 having length s1.length(). For each substring, compare its frequency map with the frequency map of s1.

Algorithm

1. Create a frequency map: "targetFrequencyMap" for "s1".

2. Iterate over each valid starting index in "s2", treating each index as the starting 
   position of the current substring.
    3. Initialize a frequency map: "currentSubstringFrequencyMap" for the current substring.
    4. Iterate over the next "s1.length()" characters in "s2" and update 
       "currentSubstringFrequencyMap".
    5. If "currentSubstringFrequencyMap" == "targetFrequencyMap", return true.

6. If no eligible substring was found, return false.

Implementation

Sample inputs
1public boolean checkInclusion(String s1, String s2) {
2
3 // 1. Create a target frequency map for s1.
4 Map<Character, Integer> targetFrequencyMap = new HashMap<>();
5 for (char ch : s1.toCharArray()) {
6 int frequency = targetFrequencyMap.getOrDefault(ch, 0) + 1;
7 targetFrequencyMap.put(ch, frequency);
8 }
9
10 // 2. Iterate over each valid starting position in s2.
11 for (int i = 0; i <= s2.length() - s1.length(); i++) {
12
13 // 3. Create a frequency map for the current substring.
14 Map<Character, Integer> currentSubstringFrequencyMap = new HashMap<>();
15
16 // 4. Iterate over next s1.length characters in s2.
17 for (int j = 0; j < s1.length(); j++) {
18 char ch = s2.charAt(i + j);
19 int frequency = currentSubstringFrequencyMap.getOrDefault(ch, 0) + 1;
20 // 5. Update current substring frequency map.
21 currentSubstringFrequencyMap.put(ch, frequency);
22 }
23
24 // 6. Check if current substring frequency map is equal to the target frequency map.
25 if (currentSubstringFrequencyMap.equals(targetFrequencyMap)) {
26 return true;
27 }
28
29 }
30
31 // 7. If no eligible substring found in s2, return false.
32 return false;
33
34}
s1
a
b
s2
e
i
d
b
a
o
o
o
0
1
2
3
4
5
6
7
Current substring—
s2[i..i + s1.length)
target vs current
Empty
i = —
j = —
checkInclusion
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/30

Time Complexity

The primary operations in the inner loop involve adding entries to currentSubstringFrequencyMap and checking if it makes targetFrequencyMap. Considering both operations take constant amount of time, O(1), the time complexity is dependent on the number of iterations of the inner and outer loops.

The outer loop runs (n - m + 1) times, where n = s2.length() and m = s1.length(). For each outer loop iteration, the inner loop runs is executed m times.

Therfore, the overall time complexity is O((n - m + 1) x m) ~ O(n x m).

Space Complexity

Both currentSubstringFrequencyMap and targetFrequencyMap can store the frequencies of upto m distinct characters simultaneously, where m = s1.length().

Therefore, the overall space complexity is O(m).

Key Optimizations

For each outer loop iteration, only one new character enters the current substring, while the remaining characters have already processed in the previous iteration.

key-optimizations

Suitable Approach - Sliding Window

Instead of rebuilding currentSubstringFrequencyMap for every substring, maintain a fixed-size sliding window of length m = s1.length().

As the window slides, add the frequency of the new character entering the window and decrement the frequency of character leaving the window. This allows us to update the currentSubstringFrequencyMap in O(1) time for each window, rather than rebuilding it in O(m) time.

Algorithm

1. Create a frequency map: "targetFrequencyMap" for "s1".

2. Initialize:
    a. Two pointers: "left = 0" and "right = 0" to represent the boundaries of the current window.
    b. A frequency map: "currentSubstringFrequencyMap" for the current window.

3. Increment the "right" pointer to expand the current window one character at a time:
    4. Add the frequency of the new character: "s2[right]" to "currentSubstringFrequencyMap".

    5. If the current window size is greater than "s1.length()":
        6. Remove the frequency of character: "s[left]" from "currentSubstringFrequencyMap".
        7. Increment "left" to remove the character: "s[left]" from the current window.

    8. If "currentSubstringFrequencyMap" == "targetFrequencyMap", return true.
    
9. If no eligible substring was found, return false.

Implementation

Sample inputs
1public boolean checkInclusion(String s1, String s2) {
2
3 // 1. Create a frequency map for s1.
4 Map<Character, Integer> targetFrequencyMap = new HashMap<>();
5 for(char ch : s1.toCharArray()) {
6 int frequency = targetFrequencyMap.getOrDefault(ch, 0) + 1;
7 targetFrequencyMap.put(ch, frequency);
8 }
9
10 // 2. Initialize two pointers: left and right to represent the boundaries of current window.
11 int left = 0, right = 0;
12
13 // 3. Initialize a frequency map to track the frequencies of the current window.
14 Map<Character, Integer> currentSubstringFrequencyMap = new HashMap<>();
15
16 // 4. Expand current window one character at a time.
17 for ( ; right < s2.length(); right++) {
18
19 // 5. Add s2[right] to the current window.
20 char newCh = s2.charAt(right);
21 int frequency = currentSubstringFrequencyMap.getOrDefault(newCh, 0) + 1;
22 currentSubstringFrequencyMap.put(newCh, frequency);
23
24 // 6. If length of current window exceeds s1.length(), remove s2[left] from the current window.
25 int currentWindowLength = right - left + 1;
26 if (currentWindowLength > s1.length()) {
27 char removeCh = s2.charAt(left);
28 frequency = currentSubstringFrequencyMap.get(removeCh) - 1;
29 if(frequency == 0) {
30 currentSubstringFrequencyMap.remove(removeCh);
31 } else {
32 currentSubstringFrequencyMap.put(removeCh, frequency);
33 }
34 left++;
35 }
36
37 // 7. Check if the current window frequency map matches the target frequency map.
38 if (currentSubstringFrequencyMap.equals(targetFrequencyMap)) {
39 return true;
40 }
41 }
42
43 // 8. If no eligible substring is found, return false
44 return false;
45
46}
s1
a
b
s2
right
right
right
right
right
right
right
right
e
i
d
b
a
o
o
o
left
left
left
left
left
left
left
left
0
1
2
3
4
5
6
7
Current window—
s2[left..right]
target vs current
Empty
left = —
right = —
currentWindowLength = —
checkInclusion
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/37

Time Complexity

The add, update and removal operations performed in each iteration take constant time, O(1), on average. The time complexity is only dependent on the movement of left and right pointers.

The right pointer traverses all n character in s2 once. The left pointer traverses at most n - m characters.

Therefore, the total number of pointer movements is at most n + (n - m), which is bounded by 2n. Since constant factors are ignored in Big-O notation, the overall time complexity is O(n).

Space Complexity

Both the currentSubstringFrequencyMap and targetFrequencyMap can hold at most m distinct characters simultaneously.

Therefore, the overall space complexity is still O(m).