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 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input:s1= "ab" s2 = "eidboaoo"
Output: False
Constraints:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].
Solution:
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] count = new int[26];
for (char c : s1.toCharArray()) {
count[c - 'a'] ++;
}
int[] count2 = new int[26];
int left = 0, right = 0;
while (right < s2.length()) {
char in = s2.charAt(right);
count2[in - 'a'] ++;
if (right - left + 1 > s1.length()) {
char out = s2.charAt(left);
count2[out - 'a'] --;
left ++;
}
int i = 0;
for (; i < 26; i ++) {
if (count[i] != count2[i]) {
break;
}
}
if (i == 26) return true;
right ++;
}
return false;
}
}