Permutation in String
You're given two strings s1 and s2 of lowercase English letters. Return true if s2 contains a substring that is a rearrangement of s1: exactly the same letters with the same counts, in any order. The match must be contiguous and exactly as long as s1. Return false otherwise, including when s1 is longer than s2.
Examples
s1 = "ab", s2 = "eidbaooo" returns true
The substring "ba" at indices 3 and 4 has one a and one b, the same letters as s1 in a different order.
s1 = "ab", s2 = "eidboaoo" returns false
The length-2 substrings are "ei", "id", "db", "bo", "oa", "ao" and "oo". None is "ab" or "ba", because an o sits between the b and the a.
Constraints
- 1 <= s1.length, s2.length <= 10^4
- s1 and s2 consist of lowercase English letters.
Hints
A permutation has the same character counts, what stays constant as you scan?
Use a fixed-size window of length s1 over s2 and compare frequency arrays.
Build need[26] from s1 and have[26] from the first |s1| chars of s2. Slide one position at a time: add the entering char, remove the leaving char, and check whether have == need.
Drill This: Your Approach First
Approach
Two strings are rearrangements of each other exactly when their letter counts match. Build 26-slot counts for s1 and for the first len(s1) letters of s2, then slide a fixed-length window along s2: add the letter entering on the right, remove the one leaving on the left, and compare the two count arrays after each step. Each comparison costs 26 operations, a constant.
Time
O(|s1| + |s2|)
Space
O(1)
Pitfall
Solutions
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] need = new int[26], have = new int[26];
for (int i = 0; i < s1.length(); i++) {
need[s1.charAt(i) - 'a']++;
have[s2.charAt(i) - 'a']++;
}
if (Arrays.equals(need, have)) return true;
for (int i = s1.length(); i < s2.length(); i++) {
have[s2.charAt(i) - 'a']++;
have[s2.charAt(i - s1.length()) - 'a']--;
if (Arrays.equals(need, have)) return true;
}
return false;
}
}class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
need = [0] * 26
have = [0] * 26
for i in range(len(s1)):
need[ord(s1[i]) - ord('a')] += 1
have[ord(s2[i]) - ord('a')] += 1
if need == have:
return True
for i in range(len(s1), len(s2)):
have[ord(s2[i]) - ord('a')] += 1
have[ord(s2[i - len(s1)]) - ord('a')] -= 1
if need == have:
return True
return False