567. Permutation in String
Problem Description
Given two strings s1
and s2
, your task is to determine whether s2
contains a permutation of s1
. In other words, you must check if any substring of s2
has the same characters as s1
, in any order. The function should return true
if at least one permutation of s1
is a substring of s2
, otherwise, it should return false
.
Intuition
The intuition behind the solution is to use a sliding window approach along with character counting. We want to slide a window of size equal to the length of s1
over s2
and check if the characters inside this window form a permutation of s1
. The key idea is to avoid recomputing the frequency of characters in the window from scratch each time we slide the window; instead, we can update the count based on the character that is entering and the character that is leaving the window.
To implement this, we use a counter data structure to keep track of the difference between the number of occurrences of each character in the current window and the number of occurrences of each character in s1
. Initially, the counter is set by decrementing for s1
characters and incrementing for the first window in s2
. We can then iterate through s2
, moving the window to the right by incrementing the count for the new character and decrementing for the character that's no longer in the window.
The difference count is the sum of the non-zero values in the counter. If at any point the difference count is zero, it means the current window is a permutation of s1
, and we return true
. If we reach the end of s2
without finding such a window, we return false
.
Learn more about Two Pointers and Sliding Window patterns.
Solution Approach
The problem is solved efficiently by using the sliding window technique, coupled with a character counter that keeps track of the frequencies of characters within the window.
Here are the key steps of the algorithm:
- Initialize a
Counter
object that will track the frequency difference of characters betweens1
and the current window ofs2
. - Set up the initial count by decrementing for each character in
s1
and incrementing for each character in the first window ofs2
. - Calculate the initial difference count, which is the sum of non-zero counts in the
Counter
. This represents how many characters' frequencies do not match betweens1
and the current window. - Start traversing
s2
with a window size ofs1
. For each step, do the following:- If the difference count is zero, return
true
. - Update the
Counter
by incrementing the count for the new character entering the window, and decrementing the count for the character leaving the window. - Adjust the difference count if the updated character counts change from zero to non-zero, or vice versa.
- If the difference count is zero, return
- If the loop completes without the difference count reaching zero, return
false
.
The implementation takes O(n + m)
time where n
is the length of s1
and m
is the length of s2
. The space complexity is O(1)
since the counter size is limited to the number of possible characters, which is constant.
The key data structures and patterns used in this solution are:
Counter
from the Pythoncollections
module to keep track of frequencies of characters.- Sliding window technique to efficiently inspect substrings of
s2
without re-counting characters each time. - Two-pointers pattern to represent the current window's start and end within
s2
.
This approach effectively checks every possible window in s2
that could be a permutation of s1
, doing so in a manner that only requires a constant amount of work for each move of the window.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example to illustrate the solution approach:
Suppose we have s1 = "abc"
and s2 = "eidbacoo"
. We are tasked with determining if s2
contains a permutation of s1
.
- First, we initialize the
Counter
object fors1
which would look likeCounter({'a':1, 'b':1, 'c':1})
as each character ins1
occurs once. - Next, we look at the first window of
s2
with the same length ass1
, which iseid
. We initialize anotherCounter
for this window, resulting inCounter({'e':1, 'i':1, 'd':1})
. - Now, we compute the initial difference count by comparing our two
Counter
objects. For characterse
,i
, andd
the count increments as they appear ins2
but nots1
. For charactersa
,b
, andc
, the counts decrement for their presence ins1
but absence in the initial window ofs2
. The sum of non-zero counts is6
, as we have three characters ins1
that are not in the window and three characters in the window that are not ins1
. - We start sliding the window in
s2
to the right, one character at a time. The next window isidb
. We increment the count forb
(as it enters the window) and decrement the count fore
(as it exits). Now theCounter
updates, and we recalculate the difference count. Charactersi
andd
still contribute to the difference count, butb
does not anymore because it matches withs1
. - Continue sliding the window to the right to the window
dba
, updating theCounter
by incrementing fora
and decrementing fori
. The counter is now matched fora
andb
, but not ford
. - Proceed to the window
bac
. Increment forc
and decrement ford
. Now theCounter
should matchs1
completely, which means the difference count will be0
. - As the difference count is
0
, it indicates that thebac
window is a permutation ofs1
. Therefore, we returntrue
.
By using the sliding window and the Counter
, we moved through s2
efficiently, avoiding recalculating the frequency of characters from scratch. We found that s2
contains a permutation of s1
, demonstrating the solution approach effectively.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def check_inclusion(self, pattern: str, text: str) -> bool:
5 # Calculate the length of both the pattern and text
6 pattern_length, text_length = len(pattern), len(text)
7
8 # If the pattern is longer than the text, the inclusion is not possible
9 if pattern_length > text_length:
10 return False
11
12 # Initialize a counter for the characters in both strings
13 char_counter = Counter()
14
15 # Decrease the count for pattern characters and increase for the first window in text
16 for pattern_char, text_char in zip(pattern, text[:pattern_length]):
17 char_counter[pattern_char] -= 1
18 char_counter[text_char] += 1
19
20 # Calculate the number of characters that are different
21 diff_count = sum(x != 0 for x in char_counter.values())
22
23 # If no characters are different, we found an inclusion
24 if diff_count == 0:
25 return True
26
27 # Slide the window over text, one character at a time
28 for i in range(pattern_length, text_length):
29 # Get the character that will be removed from the window and the one that will be added
30 char_out = text[i - pattern_length]
31 char_in = text[i]
32
33 # Update diff_count if the incoming character impacts the balance
34 if char_counter[char_in] == 0:
35 diff_count += 1
36 char_counter[char_in] += 1
37 if char_counter[char_in] == 0:
38 diff_count -= 1
39
40 # Update diff_count if the outgoing character impacts the balance
41 if char_counter[char_out] == 0:
42 diff_count += 1
43 char_counter[char_out] -= 1
44 if char_counter[char_out] == 0:
45 diff_count -= 1
46
47 # If no characters are different, we have found an inclusion
48 if diff_count == 0:
49 return True
50
51 # If inclusion has not been found by the end of the text, return False
52 return False
53
1class Solution {
2 public boolean checkInclusion(String s1, String s2) {
3 int length1 = s1.length();
4 int length2 = s2.length();
5
6 // If the first string is longer than the second string,
7 // it's not possible for s1 to be a permutation of s2.
8 if (length1 > length2) {
9 return false;
10 }
11
12 // Array to hold the difference in character counts between s1 and s2.
13 int[] charCountDelta = new int[26];
14
15 // Populate the array with initial counts
16 for (int i = 0; i < length1; ++i) {
17 charCountDelta[s1.charAt(i) - 'a']--;
18 charCountDelta[s2.charAt(i) - 'a']++;
19 }
20
21 // Counts the number of characters with non-zero delta counts.
22 int nonZeroCount = 0;
23 for (int count : charCountDelta) {
24 if (count != 0) {
25 nonZeroCount++;
26 }
27 }
28
29 // If all deltas are zero, s1 is a permutation of the first part of s2.
30 if (nonZeroCount == 0) {
31 return true;
32 }
33
34 // Slide the window of length1 through s2
35 for (int i = length1; i < length2; ++i) {
36 int charLeft = s2.charAt(i - length1) - 'a'; // Character going out of the window
37 int charRight = s2.charAt(i) - 'a'; // Character coming into the window
38
39 // Update counts for the exiting character
40 if (charCountDelta[charRight] == 0) {
41 nonZeroCount++;
42 }
43 charCountDelta[charRight]++;
44 if (charCountDelta[charRight] == 0) {
45 nonZeroCount--;
46 }
47
48 // Update counts for the entering character
49 if (charCountDelta[charLeft] == 0) {
50 nonZeroCount++;
51 }
52 charCountDelta[charLeft]--;
53 if (charCountDelta[charLeft] == 0) {
54 nonZeroCount--;
55 }
56
57 // If all deltas are zero, s1's permutation is found in s2.
58 if (nonZeroCount == 0) {
59 return true;
60 }
61 }
62
63 // If we reach here, no permutation of s1 is found in s2.
64 return false;
65 }
66}
67
1class Solution {
2public:
3 // This function checks if s1's permutation is a substring of s2
4 bool checkInclusion(string s1, string s2) {
5 int len1 = s1.size(), len2 = s2.size();
6
7 // If length of s1 is greater than s2, permutation is not possible
8 if (len1 > len2) {
9 return false;
10 }
11
12 // Vector to store character counts
13 vector<int> charCount(26, 0);
14
15 // Initialize the character count vector with the first len1 characters
16 for (int i = 0; i < len1; ++i) {
17 --charCount[s1[i] - 'a']; // Decrement for characters in s1
18 ++charCount[s2[i] - 'a']; // Increment for characters in the first window of s2
19 }
20
21 // Calculate the difference count
22 int diffCount = 0;
23 for (int count : charCount) {
24 if (count != 0) {
25 ++diffCount;
26 }
27 }
28
29 // If diffCount is zero, a permutation exists in the first window
30 if (diffCount == 0) {
31 return true;
32 }
33
34 // Slide the window over s2 and update the counts and diffCount
35 for (int i = len1; i < len2; ++i) {
36 int index1 = s2[i - len1] - 'a'; // Index for the old character in the window
37 int index2 = s2[i] - 'a'; // Index for the new character in the window
38
39 // Before updating charCount for the new character
40 if (charCount[index2] == 0) {
41 ++diffCount;
42 }
43 ++charCount[index2]; // Include the new character in the window
44
45 // After updating charCount for the new character
46 if (charCount[index2] == 0) {
47 --diffCount;
48 }
49
50 // Before updating charCount for the old character
51 if (charCount[index1] == 0) {
52 ++diffCount;
53 }
54 --charCount[index1]; // Remove the old character as we move the window
55
56 // After updating charCount for the old character
57 if (charCount[index1] == 0) {
58 --diffCount;
59 }
60
61 // If the diffCount is zero after the updates, a permutation is found
62 if (diffCount == 0) {
63 return true;
64 }
65 }
66
67 // No permutation was found
68 return false;
69 }
70};
71
1function checkInclusion(s1: string, s2: string): boolean {
2 // If s1 is longer than s2, it's impossible for s1 to be a permutation of s2.
3 if (s1.length > s2.length) {
4 return false;
5 }
6
7 // Helper function to convert characters into zero-based indices
8 function charToIndex(char: string): number {
9 return char.charCodeAt(0) - 'a'.charCodeAt(0);
10 }
11
12 // Helper function to check if both character frequency arrays match
13 function doArraysMatch(freqArray1: number[], freqArray2: number[]): boolean {
14 for (let i = 0; i < 26; i++) {
15 if (freqArray1[i] !== freqArray2[i]) {
16 return false;
17 }
18 }
19 return true;
20 }
21
22 const s1Length = s1.length;
23 const s2Length = s2.length;
24 // Arrays to store the frequency of each letter in s1 and the current window in s2
25 const freqArray1 = new Array(26).fill(0);
26 const freqArray2 = new Array(26).fill(0);
27
28 // Filling freqArray1 with frequencies of letters in s1
29 for (const char of s1) {
30 const index = charToIndex(char);
31 freqArray1[index]++;
32 }
33
34 // Filling freqArray2 with frequencies of the first window of s2 with size equal to s1 length
35 for (let i = 0; i < s1Length; i++) {
36 const index = charToIndex(s2[i]);
37 freqArray2[index]++;
38 }
39
40 // Sliding window to check each substring in s2
41 for (let left = 0, right = s1Length; right < s2Length; left++, right++) {
42 // Check if the current window is a permutation of s1
43 if (doArraysMatch(freqArray1, freqArray2)) {
44 return true;
45 }
46
47 // Slide the window forward: remove the left character and add the right character
48 const leftIndex = charToIndex(s2[left]);
49 const rightIndex = charToIndex(s2[right]);
50 freqArray2[leftIndex]--;
51 freqArray2[rightIndex]++;
52 }
53
54 // Check the last window after the loop
55 return doArraysMatch(freqArray1, freqArray2);
56}
57
Time and Space Complexity
Time Complexity
The time complexity of the provided code is O(n + m)
, where n
is the length of s1
and m
is the length of s2
. Here's why:
zip(s1, s2)
takesO(n)
time to iterate through the elements of the shorter string, which iss1
in this case as we returnFalse
immediately ifs1
is longer thans2
.- The
sum(x != 0 for x in cnt.values())
takesO(1)
time since there can be at most 26 characters (assuming lowercase English letters), so the number of different characters is constant. - The main loop runs from
n
tom
, which executesm - n + 1
times (inclusive ofn
). Each iteration of the loop has a constant number of operations that do not depend on the size ofn
orm
. Therefore, this part also takesO(m)
time. - Combining these parts, we get a total time complexity of
O(n + m)
.
Space Complexity
The space complexity of the code is O(1)
because the cnt
counter will contain at most 26 key-value pairs (if we are considering the English alphabet). The number of keys in cnt
does not grow with the size of the input strings s1
and s2
, thus it is a constant space overhead.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!