The main idea is to use a sliding window technique to compare the character frequency of a substring of s2 with the character frequency of s1. If they match, it means s2 contains a permutation of s1.
Time Complexity: O(n), where n is the length of s2, as each character in s2 is processed once.
Space Complexity: O(1), as the frequency arrays have a fixed size of 26.
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 bool checkInclusion(string s1, string s2) {
8 vector<int> count1(26, 0), count2(26, 0);
9 int len1 = s1.size(), len2 = s2.size();
10 if (len1 > len2) return false;
11
12 for (int i = 0; i < len1; ++i) {
13 count1[s1[i] - 'a']++;
14 count2[s2[i] - 'a']++;
15 }
16
17 for (int i = len1; i < len2; ++i) {
18 if (count1 == count2) return true;
19 count2[s2[i] - 'a']++;
20 count2[s2[i - len1] - 'a']--;
21 }
22 return count1 == count2;
23 }
24};Similar to the C solution, this C++ solution uses two vectors of size 26 to count the frequency of characters. It slides a window over s2 and updates the vector for the window while checking for equality with the vector for s1.
Leverage a hash map (or dictionary) to record the character count of s1 and use it to compare with segments of s2. This approach focuses on incremental updates to the map as the window slides over s2.
Time Complexity: O(n), where n is the length of s2.
Space Complexity: O(1), since the hash map's size is bounded by the character set size of 26.
1var checkInclusion = function(s1, s2) {
2 let len1 = s1.length, len2 = s2.length;
3 if (len1 > len2) return false;
4 const count1 = {}, count2 = {};
5 for (let i = 0; i < len1; i++) {
6 count1[s1[i]] = (count1[s1[i]] || 0) + 1;
7 count2[s2[i]] = (count2[s2[i]] || 0) + 1;
8 }
9 let matches = 0;
10 for (let key in count1) {
11 if (count1[key] === count2[key]) matches++;
12 }
13 for (let i = len1; i < len2; i++) {
14 if (matches === Object.keys(count1).length) return true;
15 let inChar = s2[i];
16 count2[inChar] = (count2[inChar] || 0) + 1;
17 if (count1[inChar] === count2[inChar]) matches++;
18 else if (count1[inChar] + 1 === count2[inChar]) matches--;
19
20 let outChar = s2[i - len1];
21 count2[outChar]--;
22 if (count1[outChar] === count2[outChar]) matches++;
23 else if (count1[outChar] - 1 === count2[outChar]) matches--;
24 }
25 return matches === Object.keys(count1).length;
26};This JavaScript solution adopts a similar strategy to the Python solution using objects to store character counts and keeps a running number of matched frequencies, sliding the window across s2.