Description
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.
Constraints
1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.
Approach
Links
Examples
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Solutions
/**
* Time complexity :
* Space complexity : O(1)
*/
class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] counter = new int[26];
for(char ch: s1.toCharArray()) {
counter[ch-'a']++;
}
int s1Len = s1.length(), s2Len = s2.length();
for(int i = 0; i < s2Len; i++) {
char ch = s2.charAt(i);
counter[ch-'a']--;
if(i >= s1Len) {
counter[s2.charAt(i-s1Len) - 'a']++;
}
if(isPermutation(counter)) {
return true;
}
}
return false;
}
private boolean isPermutation(int[] counter) {
for(int i = 0; i < 26; i++) {
if(counter[i] != 0) {
return false;
}
}
return true;
}
}
Follow up