Problem
Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring. Otherwise, return false.In other words, we need to find whether any substring of s2 has exactly the same character frequencies as s1.
Example
Consider the following example to understand the expected input and output.Input
s1 = "ab"
s2 = "eidbaooo"Output
trueSolution
This solution uses the Sliding Window technique along with a character frequency array. Since a permutation must have exactly the same character frequencies as s1, we maintain the frequency of characters in a window of the same length as s1.First, we store the frequency of each character in s1. We then move a fixed-size window through s2. For every new character entering the window, its frequency is increased. When the window size becomes larger than s1.length(), the character at the left side of the window is removed.
After maintaining a window of exactly the same size as s1, we compare the character frequencies of the window with those of s1. If they are equal, the current window is a permutation of s1.
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
int[] count1 = new int[26];
int[] count2 = new int[26];
for (char c : s1.toCharArray()) {
count1[c - 'a']++;
}
for (int right = 0; right < s2.length(); right++) {
count2[s2.charAt(right) - 'a']++;
// Keep the window size equal to s1.length().
if (right >= s1.length()) {
count2[s2.charAt(right - s1.length()) - 'a']--;
}
if (Arrays.equals(count1, count2)) {
return true;
}
}
return false;
}Complexity
The sliding window traverses s2 once. Comparing the two frequency arrays takes constant time because the arrays contain only 26 lowercase English letters. Therefore, the overall time complexity is O(n), where n is the length of s2.The solution uses two arrays of size 26, so the extra space complexity is O(1).
