Problem

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.

Examples

Example 1:

1
2
3

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

1
2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Solution

Method 1 - Sliding Window and 2 counting arrays

Here is the approach:

  1. Character Frequency Count:
    • First, compute the frequency of each character in s1 and store it in an array or counter. This array will have a fixed size of 26 to represent each lowercase English letter.
  2. Initial Window Setup:
    • Next, consider the first window of length equal to s1 in s2 and compute the frequency of characters in this window. This window represents the first possible substring of s2 that we will test to see if it matches s1.
  3. Window Sliding Technique:
    • Compare the frequency array of the first window in s2 with the frequency array of s1. If they are equal, it means a permutation of s1 is found in s2, so return true.
    • If not, slide the window one character to the right. For each slide:
      • Increment the count of the new character added to the window.
      • Decrement the count of the character that is no longer in the window.
      • Compare the updated frequency array for the new window with s1’s frequency array.
    • If at any point the frequency arrays match, return true.
  4. Completion:
    • If no matching window is found by the time we slide through the entire s2, return false as no permutation of s1 is a substring of s2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];

        // Count frequency of each character in s1
        for (char c : s1.toCharArray()) {
            s1Count[c - 'a']++;
        }

        // Initial window count for s2
        for (int i = 0; i < s1.length(); i++) {
            s2Count[s2.charAt(i) - 'a']++;
        }

        // Compare arrays of the first window
        if (Arrays.equals(s1Count, s2Count)) {
            return true;
        }

        // Slide the window over s2
        for (int i = s1.length(); i < s2.length(); i++) {
            s2Count[s2.charAt(i) - 'a']++;
            s2Count[s2.charAt(i - s1.length()) - 'a']--;

            if (Arrays.equals(s1Count, s2Count)) {
                return true;
            }
        }

        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        s1_count = Counter(s1)
        s2_count = Counter(s2[:len(s1)])

        if s1_count == s2_count:
            return True

        for i in range(len(s1), len(s2)):
            s2_count[s2[i]] += 1
            s2_count[s2[i - len(s1)]] -= 1

            if s2_count[s2[i - len(s1)]] == 0:
                del s2_count[s2[i - len(s1)]]

            if s1_count == s2_count:
                return True

        return False

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s2. This is because we iterate through the s2 string a single time while maintaining a frequency count which is an O(1) operation due to the constant size of the alphabet (26 letters).
  • 🧺 Space complexity: O(1), because we’re using fixed-size arrays, to store the frequency of characters, which do not scale with input size.

Method 2 - Sliding window and 1 counting array

  1. Permutation Check: To verify if string p is a permutation of string s, ensure every character in p exists in s. We can represent all permutations of s using a frequency map (Character -> Count). For example, abba becomes {a:2, b:2}. Given that there are only 26 lowercase letters, an array can efficiently represent this map.
  2. Containment Check: To determine if s2 contains a permutation of s1, use a sliding window of length s1 across s2. As characters enter the window from the right, decrease their count in the map; as they exit from the left, increase their count. When all counts in the map reach zero, it indicates a matching frequency of characters between s

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
	public boolean checkInclusion(String s1, String s2) {
		int len1 = s1.length(), len2 = s2.length();
		if (len1 > len2) {
			return false;
		}
		
		int[] count = new int[26];
		for (int i = 0; i < len1; i++) {
			count[s1.charAt(i) - 'a']++;
			count[s2.charAt(i) - 'a']--;
		}
		if (allZero(count)) {
			return true;
		}
		
		for (int i = len1; i < len2; i++) {
			count[s2.charAt(i) - 'a']--;
			count[s2.charAt(i - len1) - 'a']++;
			if (allZero(count)) {
				return true;
			}
		}
		
		return false;
	}
	
	private boolean allZero(int[] count) {
		for (int i = 0; i < 26; i++) {
			if (count[i] != 0) return false;
		}
		return true;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        len1, len2 = len(s1), len(s2)
        if len1 > len2:
            return False
        
        count = [0] * 26  # Array to store character counts
        
        # Initialize the count array with the first window
        for i in range(len1):
            count[ord(s1[i]) - ord('a')] += 1
            count[ord(s2[i]) - ord('a')] -= 1
        
        if self.allZero(count):
            return True
        
        # Slide the window over s2
        for i in range(len1, len2):
            count[ord(s2[i]) - ord('a')] -= 1
            count[ord(s2[i - len1]) - ord('a')] += 1
            if self.allZero(count):
                return True
        
        return False
    
    def allZero(self, count):
        for x in count:
            if x != 0:
                return False
        return True

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1), as the count array size is fixed at 26, which is a constant. The space does not grow with the input size.

Method 3 - Using 1 count array and sliding window technique reducing need to match 26 chars explicitly

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] count = new int[26];  // Array to hold the count of characters in s1
        for (char c : s1.toCharArray()) {
            count[c - 'a']++;
        }
        
        int l = 0, r = 0;
        int m = s1.length(), n = s2.length();
        int diffs = m;  // Number of differing characters
        
        // Iterate over s2 with two pointers
        while (r < s2.length()) {
            // Decrement the count of the character entering the window
            if (count[s2.charAt(r++) - 'a']-- > 0) {
                diffs--;
            }
            // If diffs is zero, we found a valid permutation match
            if (diffs == 0) {
	            return true;
	        }
            // When the window size exceeds s1.length(), update the left pointer
            if (r - l == m && count[s2.charAt(l++) - 'a']++ >= 0) {
	            diffs++;
            }
        }
        
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count = [0] * 26  # Array to hold the count of characters in s1
        for c in s1:
            count[ord(c) - ord('a')] += 1
        
        l, r = 0, 0
        diffs = len(s1)  # Number of differing characters
        
        # Iterate over s2 with two pointers
        while r < len(s2):
            # Decrement the count of the character entering the window
            if count[ord(s2[r]) - ord('a')] > 0:
                diffs -= 1
            count[ord(s2[r]) - ord('a')] -= 1
            r += 1
            # If diffs is zero, we found a valid permutation match
            if diffs == 0:
                return True
            
            # When the window size exceeds s1.length(), update the left pointer
            if r - l == len(s1):
                if count[ord(s2[l]) - ord('a')] >= 0:
                    diffs += 1
                count[ord(s2[l]) - ord('a')] += 1
                l += 1
        
        return False

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)