Permutation in String
Permutation in String is a medium arrays & hashing problem solved with the sliding window · fixed pattern.
The best approach, optimal (fixed sliding window with match counter), runs in O(n + m) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort every window) up.
Problem
Given two strings s1 and s2, return true if some contiguous substring of s2 is a permutation of s1 (uses exactly the same letters with the same counts, in any order). Otherwise return false.
Examples
Example 1
- Input
s1 = "tea", s2 = "sweater"- Output
true- Why
- The window "eat" (indices 2 to 4) is a rearrangement of "tea".
Example 2
- Input
s1 = "aab", s2 = "abacb"- Output
true- Why
- The window "aba" at indices 0 to 2 uses two 'a's and one 'b', the same letters as "aab".
Example 3
- Input
s1 = "dog", s2 = "goodday"- Output
false- Why
- The windows of length 3 are goo, ood, odd, dda and day; none has exactly one 'd', one 'o' and one 'g'.
Constraints
1 <= s1.length, s2.length <= 10^4s1ands2consist only of lowercase English letters
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (sort every window) | O((n - m + 1) · m log m) | O(m) |
| Optimal (fixed sliding window with match counter) | O(n + m) | O(1) |
1Brute force (sort every window)
O((n - m + 1) · m log m)Each of the n - m + 1 windows (n = |s2|, m = |s1|) is copied and sorted.O(m)One sorted copy of a window and of s1.Sort s1 once. For each window of s2 with length |s1|, sort the window and compare it with the sorted s1. Two strings are permutations of each other exactly when their sorted forms are equal.
- If |s1| > |s2|, return false.
- Sort the letters of s1.
- For every start i from 0 to |s2| - |s1|, sort s2[i .. i + |s1| - 1].
- If it equals sorted s1, return true.
- Return false.
class Solution {
public boolean checkInclusion(String s1, String s2) {
int m = s1.length(), n = s2.length();
if (m > n) return false;
char[] target = s1.toCharArray();
Arrays.sort(target);
for (int i = 0; i + m <= n; i++) {
char[] window = s2.substring(i, i + m).toCharArray();
Arrays.sort(window);
if (Arrays.equals(window, target)) return true;
}
return false;
}
}class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m > n:
return False
target = sorted(s1)
for i in range(n - m + 1):
if sorted(s2[i:i + m]) == target:
return True
return Falseclass Solution {
public:
bool checkInclusion(string s1, string s2) {
int m = s1.size(), n = s2.size();
if (m > n) return false;
string target = s1;
sort(target.begin(), target.end());
for (int i = 0; i + m <= n; i++) {
string window = s2.substr(i, m);
sort(window.begin(), window.end());
if (window == target) return true;
}
return false;
}
};function checkInclusion(s1, s2) {
const m = s1.length, n = s2.length;
if (m > n) return false;
const target = s1.split('').sort().join('');
for (let i = 0; i + m <= n; i++) {
const window = s2.slice(i, i + m).split('').sort().join('');
if (window === target) return true;
}
return false;
}2Optimal (fixed sliding window with match counter)
O(n + m)Each character of s2 enters and leaves the window once; every update is O(1).O(1)Two arrays of 26 counts.Keep two arrays of 26 letter counts: one for s1 and one for the current window of s2 of length |s1|. Also keep matches, the number of letters whose two counts are equal. Each slide changes only two counts, so matches can be updated in O(1). The answer is true as soon as matches == 26.
- If |s1| > |s2|, return false.
- Count the letters of s1 and of the first |s1| letters of s2; compute matches over the 26 letters.
- For each next index r: if matches == 26 return true; add s2[r] to the window and remove s2[r - |s1|], adjusting matches when a count becomes equal or stops being equal.
- Return matches == 26 after the last window.
class Solution {
public boolean checkInclusion(String s1, String s2) {
int m = s1.length(), n = s2.length();
if (m > n) return false;
int[] need = new int[26], have = new int[26];
for (int i = 0; i < m; i++) {
need[s1.charAt(i) - 'a']++;
have[s2.charAt(i) - 'a']++;
}
int matches = 0;
for (int c = 0; c < 26; c++) if (need[c] == have[c]) matches++;
for (int r = m; r < n; r++) {
if (matches == 26) return true;
int in = s2.charAt(r) - 'a';
have[in]++;
if (have[in] == need[in]) matches++;
else if (have[in] == need[in] + 1) matches--;
int out = s2.charAt(r - m) - 'a';
have[out]--;
if (have[out] == need[out]) matches++;
else if (have[out] == need[out] - 1) matches--;
}
return matches == 26;
}
}class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m > n:
return False
need, have = [0] * 26, [0] * 26
for i in range(m):
need[ord(s1[i]) - 97] += 1
have[ord(s2[i]) - 97] += 1
matches = sum(1 for c in range(26) if need[c] == have[c])
for r in range(m, n):
if matches == 26:
return True
a = ord(s2[r]) - 97
have[a] += 1
if have[a] == need[a]:
matches += 1
elif have[a] == need[a] + 1:
matches -= 1
b = ord(s2[r - m]) - 97
have[b] -= 1
if have[b] == need[b]:
matches += 1
elif have[b] == need[b] - 1:
matches -= 1
return matches == 26class Solution {
public:
bool checkInclusion(string s1, string s2) {
int m = s1.size(), n = s2.size();
if (m > n) return false;
int need[26] = {0}, have[26] = {0};
for (int i = 0; i < m; i++) {
need[s1[i] - 'a']++;
have[s2[i] - 'a']++;
}
int matches = 0;
for (int c = 0; c < 26; c++) if (need[c] == have[c]) matches++;
for (int r = m; r < n; r++) {
if (matches == 26) return true;
int in = s2[r] - 'a';
have[in]++;
if (have[in] == need[in]) matches++;
else if (have[in] == need[in] + 1) matches--;
int out = s2[r - m] - 'a';
have[out]--;
if (have[out] == need[out]) matches++;
else if (have[out] == need[out] - 1) matches--;
}
return matches == 26;
}
};function checkInclusion(s1, s2) {
const m = s1.length, n = s2.length;
if (m > n) return false;
const need = new Array(26).fill(0), have = new Array(26).fill(0);
for (let i = 0; i < m; i++) {
need[s1.charCodeAt(i) - 97]++;
have[s2.charCodeAt(i) - 97]++;
}
let matches = 0;
for (let c = 0; c < 26; c++) if (need[c] === have[c]) matches++;
for (let r = m; r < n; r++) {
if (matches === 26) return true;
const a = s2.charCodeAt(r) - 97;
have[a]++;
if (have[a] === need[a]) matches++;
else if (have[a] === need[a] + 1) matches--;
const b = s2.charCodeAt(r - m) - 97;
have[b]--;
if (have[b] === need[b]) matches++;
else if (have[b] === need[b] - 1) matches--;
}
return matches === 26;
}Edge cases to test
- s1 longer than s2 (always false)
- s1 and s2 of the same length
- Repeated letters in s1, where counts (not just presence) must match
- The matching window is at the very start or the very end of s2
Hints
Hint 1
A permutation of s1 is any string with exactly the same letter counts as s1.
Hint 2
Only windows of s2 with length |s1| can match. Compare letter counts instead of generating permutations.
Hint 3
Slide the window one step at a time: add the new letter, remove the old one, and track how many of the 26 counts currently agree.
FAQ
What is the best time complexity for Permutation in String?
Optimal (fixed sliding window with match counter) runs in O(n + m) time and O(1) extra space. Each character of s2 enters and leaves the window once; every update is O(1).
Which pattern does Permutation in String use?
It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.
Is there a brute force solution for Permutation in String?
Yes. Brute force (sort every window) takes O((n - m + 1) · m log m) time and O(m) space. Sort s1 once.
Which edge cases should I test for Permutation in String?
s1 longer than s2 (always false); s1 and s2 of the same length; Repeated letters in s1, where counts (not just presence) must match; The matching window is at the very start or the very end of s2.