Log inSign up
mediumleetcodeNot Started

Permutation in String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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 · Example:

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

Example 2 · Example:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Explanation: No substring of length 2 in s2 is a permutation of "ab".

Constraints:

  • 1 <= s1.length, s2.length <= 104
  • s1 and s2 consist of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply fixed-size sliding windows to anagram matching.
  • Maintain a running match count to achieve pure O(N) execution.
  • Handle boundary conditions when window size exceeds string length.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Check if any substring is an anagram/permutation of a target pattern.
  • Fixed-length window substring frequency comparison.

Algorithmic Decision Tree:

  • Fixed Size Sliding Window
  • Running Frequency Matching

Connected Patterns:

Find All Anagrams in a StringValid AnagramMinimum Window Substring

1. Sort Every Window of Length M

Intuition

Sort s1 into sortedS1. For each index i from 0 to s2.length - s1.length: extract substring s2[i...i+M-1], sort it, and compare with sortedS1. If equal, return true.

When to apply: Basic baseline comparison.

Algorithm

  1. If s1.length > s2.length: return false.
  2. sortedS1 = sort(s1).
  3. For i from 0 to s2.length - s1.length:
  4. sub = sort(s2.substr(i, s1.length)).
  5. If sub == sortedS1: return true.
  6. Return false.

Sort Every Window of Length M

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [e, i, d, b, a, o, o, o]
Current operationSTEP 1 OF 6
Observation: Target s1 = 'ab' has length $M = 2$ and sorts to 'ab'
Visual state
Values and pointers at this exact step
array
S
e
i
d
b
a
o
o
o
0
↑ L=0
1
↑ R=1
2
3
4
5
6
7
Variables at this step
window
ei
sortedWindow
ei
target
ab
match
false
L
0
R
1
Check / comparison
Window 'ei' sorted -> 'ei'. Target 'ab' sorted -> 'ab'.
Decision / next transition
'ei' != 'ab'. Window does not form permutation; advance rightward.
Why this step matters

Observation: Target s1 = 'ab' has length M = 2 and sorts to 'ab'. Inspect initial window s2[0..1] = 'ei'.

Decision: Sort window substring: 'ei'. Compare against sorted target 'ab'. Mismatch detected.

Invariant: A substring is a permutation of s_1 if and only if their sorted character sequences are identical.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 bool checkInclusion(std::string s1, std::string s2) {
8 int m = s1.size(), n = s2.size();
9 if (m > n) return false;
10
11 std::string sortedS1 = s1;
12 std::sort(sortedS1.begin(), sortedS1.end());
13
14 for (int i = 0; i <= n - m; ++i) {
15 std::string sub = s2.substr(i, m);
16 std::sort(sub.begin(), sub.end());
17 if (sub == sortedS1) return true;
18 }
19 return false;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::cout << (sol.checkInclusion("ab", "eidbaooo") ? "true" : "false") << std::endl; // true
26 std::cout << (sol.checkInclusion("ab", "eidboaoo") ? "true" : "false") << std::endl; // false
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M log M) — Extracts and sorts N - M + 1 substrings of length M.
  • Space complexity: O(M)

Why Brute Force Doesn't Scale:

Tracking matches variable eliminates the 26-element array loop.

Two 26-integer stack arrays.

2. Sliding Window with 26-Array Array Equality

Intuition

Count character frequencies of s1 in s1Count[26] and first window of s2 in s2Count[26]. Slide window: add incoming character, remove outgoing character, and compare s1Count == s2Count.

When to apply: Standard intuitive sliding window implementation.

Algorithm

  1. If s1.length > s2.length: return false.
  2. Populate s1Count and initial s2Count for window of length m.
  3. If s1Count == s2Count: return true.
  4. For i from m to n - 1:
  5. s2Count[s2[i] - 'a']++.
  6. s2Count[s2[i - m] - 'a']--.
  7. If s1Count == s2Count: return true.
  8. Return false.

Sliding Window with 26-Array Equality

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [e, i, d, b, a, o, o, o]
Current operationSTEP 1 OF 6
Observation: Initialize frequency vector of length 26
Visual state
Values and pointers at this exact step
array
S
e
i
d
b
a
o
o
o
0
↑ L=0
1
↑ R=1
2
3
4
5
6
7
Variables at this step
targetCounts
{"a":1,"b":1}
windowCounts
{"e":1,"i":1}
arraysEqual
false
L
0
R
1
Check / comparison
Target counts: a:1, b:1. Window [0..1] counts: e:1, i:1.
Decision / next transition
Compare two 26-element integer arrays. Frequencies do not match; slide window.
Why this step matters

Observation: Initialize frequency vector of length 26. count1 has a:1, b:1. Populate first window s2[0..1] with e:1, i:1.

Decision: Compare arrays element-by-element in O(26) = O(1) time. Arrays differ.

Invariant: Character frequency counting avoids O(M log M) string sorting on each window.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 bool checkInclusion(std::string s1, std::string s2) {
8 int m = s1.size(), n = s2.size();
9 if (m > n) return false;
10
11 std::vector<int> s1Count(26, 0), s2Count(26, 0);
12 for (int i = 0; i < m; ++i) {
13 s1Count[s1[i] - 'a']++;
14 s2Count[s2[i] - 'a']++;
15 }
16
17 if (s1Count == s2Count) return true;
18
19 for (int i = m; i < n; ++i) {
20 s2Count[s2[i] - 'a']++;
21 s2Count[s2[i - m] - 'a']--;
22 if (s1Count == s2Count) return true;
23 }
24 return false;
25 }
26};
27
28int main() {
29 Solution sol;
30 std::cout << (sol.checkInclusion("ab", "eidbaooo") ? "true" : "false") << std::endl; // true
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(26 * N) — N steps each performing 26 comparisons.
  • Space complexity: O(1) (two 26-element arrays)

3. Sliding Window with Matches Count (Optimal O(N))

Intuition

Initialize matches = 0 representing how many of the 26 character frequencies are currently identical between s1 and the window in s2. For each character entering or leaving the window, update s2Count and increment/decrement matches if the count becomes equal to or differs from s1Count. When matches == 26, an exact permutation is found.

When to apply: The standard gold standard solution.

Algorithm

  1. If s1.length > s2.length: return false.
  2. Populate s1Count and initial s2Count for window of size M.
  3. Count initial matches across all 26 characters (0 to 26).
  4. For i from m to n - 1:
  5. If matches == 26: return true.
  6. Process incoming s2[i]: adjust matches before and after incrementing count.
  7. Process outgoing s2[i - m]: adjust matches before and after decrementing count.
  8. Return matches == 26.

Fixed-Size Rolling Frequency Window Match

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [e, i, d, b, a, o, o, o]
Current operationSTEP 1 OF 6
Observation: Target s1 = "ab" has length 2: counts { a: 1, b: 1 }
Visual state
Values and pointers at this exact step
array
S
e
i
d
b
a
o
o
o
0
↑ L=0
1
↑ R=1 (Window 1: "ei")
2
3
4
5
6
7
Variables at this step
targetFreq
{"a":1,"b":1}
windowFreq
{"e":1,"i":1}
matches
24
matchTarget
26
match
false
Why this step matters

Observation: Target s1 = "ab" has length 2: counts { a: 1, b: 1 }. Examine first window [0, 1] ("ei").

Decision: Window counts { e: 1, i: 1 } do not match { a: 1, b: 1 }. Slide window right.

Invariant: Fixed window size is always exactly s1.length = 2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 bool checkInclusion(std::string s1, std::string s2) {
8 int m = s1.size(), n = s2.size();
9 if (m > n) return false;
10
11 int s1Count[26] = {0}, s2Count[26] = {0};
12 for (int i = 0; i < m; ++i) {
13 s1Count[s1[i] - 'a']++;
14 s2Count[s2[i] - 'a']++;
15 }
16
17 int matches = 0;
18 for (int i = 0; i < 26; ++i) {
19 if (s1Count[i] == s2Count[i]) matches++;
20 }
21
22 for (int i = m; i < n; ++i) {
23 if (matches == 26) return true;
24
25 // Add right character
26 int r = s2[i] - 'a';
27 s2Count[r]++;
28 if (s2Count[r] == s1Count[r]) {
29 matches++;
30 } else if (s2Count[r] == s1Count[r] + 1) {
31 matches--;
32 }
33
34 // Remove left character
35 int l = s2[i - m] - 'a';
36 s2Count[l]--;
37 if (s2Count[l] == s1Count[l]) {
38 matches++;
39 } else if (s2Count[l] == s1Count[l] - 1) {
40 matches--;
41 }
42 }
43 return matches == 26;
44 }
45};
46
47int main() {
48 Solution sol;
49 std::cout << (sol.checkInclusion("ab", "eidbaooo") ? "true" : "false") << std::endl; // true
50 std::cout << (sol.checkInclusion("ab", "eidboaoo") ? "true" : "false") << std::endl; // false
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N) strictly — Each character shift performs strictly O(1) operations.
  • Space complexity: O(1) extra space (26 integers)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sort Substrings (Brute Force)O((N - M + 1) * M log M)O(M)Sorts each window of length M.High overhead per window.
2.Sliding Window with 26-Array Equality CheckO(26 * (N - M))O(1)Simpler to write; checks array equality in 26 steps.Performs 26 comparisons per window slide.
3.Sliding Window with Matches Count (Optimal O(N))OptimalO(N) strictlyO(1) extra spaceStrictly O(1) amortized and worst-case per character shift.Requires tracking match increments and decrements carefully.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not checking s1.length > s2.length at the start.

Pitfall 2:

Updating matches count incorrectly when count transitions across s1Count.

Crucial Edge Cases to Validate:

  • s1 longer than s2: Length check returns false immediately in O(1).
  • s1 and s2 identical strings: Initial matches == 26 returns true on first check.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why the fixed window length equals s1.length.
  2. Demonstrate the O(1) matches counter state updates.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the matches counter range from 0 to 26 rather than counting matched letters?

Back to DSA Sheet