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.
1using System;
2using System.Linq;
3
4public class Solution {
5 public bool CheckInclusion(string s1, string s2) {
6 if (s1.Length > s2.Length) return false;
7 int[] count1 = new int[26];
8 int[] count2 = new int[26];
9 for (int i = 0; i < s1.Length; ++i) {
10 count1[s1[i] - 'a']++;
11 count2[s2[i] - 'a']++;
12 }
13 for (int i = s1.Length; i < s2.Length; ++i) {
14 if (count1.SequenceEqual(count2)) return true;
15 count2[s2[i] - 'a']++;
16 count2[s2[i - s1.Length] - 'a']--;
17 }
18 return count1.SequenceEqual(count2);
19 }
20}This C# solution implements the same logic using arrays and checks their content with LINQ's SequenceEqual method for permutation checking.
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.
1from collections import defaultdict
2
3class Solution:
4 def checkInclusion(self, s1: str, s2: str) -> bool:
5 if len(s1) > len(s2):
6 return False
7 count1 = defaultdict(int)
8 count2 = defaultdict(int)
9 for ch in s1:
10 count1[ch] += 1
11 for ch in s2[:len(s1)]:
12 count2[ch] += 1
13 matches = 0
14 for key in count1:
15 if count1[key] == count2[key]:
16 matches += 1
17 l = 0
18 for r in range(len(s1), len(s2)):
19 if matches == len(count1):
20 return True
21 new_char = s2[r]
22 count2[new_char] += 1
23 if count2[new_char] == count1[new_char]:
24 matches += 1
25 elif count2[new_char] == count1[new_char] + 1:
26 matches -= 1
27
28 old_char = s2[l]
29 count2[old_char] -= 1
30 if count2[old_char] == count1[old_char]:
31 matches += 1
32 elif count2[old_char] == count1[old_char] - 1:
33 matches -= 1
34 l += 1
35 return matches == len(count1)This Python solution optimizes character comparison by leveraging a hash map to keep track of character frequency changes as the sliding window moves. Instead of full map comparison for each slide, it increments and decrements values while checking conditions, which reduces the overhead of comparing full data structures.