Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.
Example 1:
Input: s1 = “xyz” s2 = “pfijyxzskm”
Output: True
Example 2:
Input: s1 = “xyz” s2 = “pfyijxzskm”
Output: False
Constraints:
- The input strings only contain lower case letters.
- The length of both given strings is in range [1, 10,000].
Solution:
We will traverse through the second string from the start. If we found any of the character which is there in the first string, we go for checking others characters too. No matter how there sequences are, as all the possible permutation is valid of string s1 in string s2. We will create a slinding window of length equal to the length of string s1.
When a character moves out from left of the window, we add 1 to that character count. So once we see all zeros in the map, this means the number of characters of string s1 and the substring in the sliding window of string s2 are equal and we return true for this.
Solution Implementation
public 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;
}
}Complexity Analysis:
Time Complexity: O(n)
Space Complexity: O(1)
