Description
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:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:
1 <= s1.length, s2.length <= 104s1 and s2 consist of lowercase English letters.
Solutions
Solution 1: Sliding Window
We use an array cnt to record the characters and their counts that need to be matched, and a variable need to record the number of different characters that still need to be matched. Initially, cnt contains the character counts from the string s1, and need is the number of different characters in s1.
Then we traverse the string s2. For each character, we decrement its corresponding value in cnt. If the decremented value equals 0, it means the current character's count in s1 is satisfied, and we decrement need. If the current index i is greater than or equal to the length of s1, we need to increment the corresponding value in cnt for s2[i-s1]. If the incremented value equals 1, it means the current character's count in s1 is no longer satisfied, and we increment need. During the traversal, if the value of need equals 0, it means all character counts are satisfied, and we have found a valid substring, so we return true.
Otherwise, if the traversal ends without finding a valid substring, we return false.
The time complexity is O(m + n), where m and n are the lengths of strings s1 and s2, respectively. The space complexity is O(|Σ|), where Σ is the character set. In this problem, the character set is lowercase letters, so the space complexity is constant.
PythonJavaC++GoTypeScriptRustC#PHP
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
cnt = Counter(s1)
need = len(cnt)
m = len(s1)
for i, c in enumerate(s2):
cnt[c] -= 1
if cnt[c] == 0:
need -= 1
if i >= m:
cnt[s2[i - m]] += 1
if cnt[s2[i - m]] == 1:
need += 1
if need == 0:
return True
return False(code-box)
class Solution {
public boolean checkInclusion(String s1, String s2) {
int need = 0;
int[] cnt = new int[26];
for (char c : s1.toCharArray()) {
if (++cnt[c - 'a'] == 1) {
++need;
}
}
int m = s1.length(), n = s2.length();
for (int i = 0; i < n; ++i) {
int c = s2.charAt(i) - 'a';
if (--cnt[c] == 0) {
--need;
}
if (i >= m) {
c = s2.charAt(i - m) - 'a';
if (++cnt[c] == 1) {
++need;
}
}
if (need == 0) {
return true;
}
}
return false;
}
}(code-box)
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int need = 0;
int cnt[26]{};
for (char c : s1) {
if (++cnt[c - 'a'] == 1) {
++need;
}
}
int m = s1.size(), n = s2.size();
for (int i = 0; i < n; ++i) {
int c = s2[i] - 'a';
if (--cnt[c] == 0) {
--need;
}
if (i >= m) {
c = s2[i - m] - 'a';
if (++cnt[c] == 1) {
++need;
}
}
if (need == 0) {
return true;
}
}
return false;
}
};(code-box)
func checkInclusion(s1 string, s2 string) bool {
need := 0
cnt := [26]int{}
for _, c := range s1 {
if cnt[c-'a']++; cnt[c-'a'] == 1 {
need++
}
}
m, n := len(s1), len(s2)
for i := 0; i < n; i++ {
c := s2[i] - 'a'
if cnt[c]--; cnt[c] == 0 {
need--
}
if i >= m {
c = s2[i-m] - 'a'
if cnt[c]++; cnt[c] == 1 {
need++
}
}
if need == 0 {
return true
}
}
return false
}(code-box)
function checkInclusion(s1: string, s2: string): boolean {
let need = 0;
const cnt: number[] = Array(26).fill(0);
const a = 'a'.charCodeAt(0);
for (const c of s1) {
if (++cnt[c.charCodeAt(0) - a] === 1) {
need++;
}
}
const [m, n] = [s1.length, s2.length];
for (let i = 0; i < n; i++) {
let c = s2.charCodeAt(i) - a;
if (--cnt[c] === 0) {
need--;
}
if (i >= m) {
c = s2.charCodeAt(i - m) - a;
if (++cnt[c] === 1) {
need++;
}
}
if (need === 0) {
return true;
}
}
return false;
}(code-box)
impl Solution {
pub fn check_inclusion(s1: String, s2: String) -> bool {
let mut need = 0;
let mut cnt = vec![0; 26];
for c in s1.chars() {
let index = (c as u8 - b'a') as usize;
if cnt[index] == 0 {
need += 1;
}
cnt[index] += 1;
}
let m = s1.len();
let n = s2.len();
let s2_bytes = s2.as_bytes();
for i in 0..n {
let c = (s2_bytes[i] - b'a') as usize;
cnt[c] -= 1;
if cnt[c] == 0 {
need -= 1;
}
if i >= m {
let c = (s2_bytes[i - m] - b'a') as usize;
cnt[c] += 1;
if cnt[c] == 1 {
need += 1;
}
}
if need == 0 {
return true;
}
}
false
}
}(code-box)
public class Solution {
public bool CheckInclusion(string s1, string s2) {
int need = 0;
int[] cnt = new int[26];
foreach (char c in s1) {
if (++cnt[c - 'a'] == 1) {
need++;
}
}
int m = s1.Length, n = s2.Length;
for (int i = 0; i < n; i++) {
int c = s2[i] - 'a';
if (--cnt[c] == 0) {
need--;
}
if (i >= m) {
c = s2[i - m] - 'a';
if (++cnt[c] == 1) {
need++;
}
}
if (need == 0) {
return true;
}
}
return false;
}
}(code-box)
class Solution {
/**
* @param String $s1
* @param String $s2
* @return Boolean
*/
function checkInclusion($s1, $s2) {
$need = 0;
$cnt = array_fill(0, 26, 0);
for ($i = 0; $i < strlen($s1); $i++) {
$index = ord($s1[$i]) - ord('a');
if (++$cnt[$index] == 1) {
$need++;
}
}
$m = strlen($s1);
$n = strlen($s2);
for ($i = 0; $i < $n; $i++) {
$c = ord($s2[$i]) - ord('a');
if (--$cnt[$c] == 0) {
$need--;
}
if ($i >= $m) {
$c = ord($s2[$i - $m]) - ord('a');
if (++$cnt[$c] == 1) {
$need++;
}
}
if ($need == 0) {
return true;
}
}
return false;
}
}(code-box)
