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
class Solution {
public boolean checkInclusion(String s1, String s2) {
Map<Character, Integer> map = new HashMap<>();
for (char ch : s1.toCharArray()) {
int val = map.getOrDefault(ch, 0);
map.put(ch, val + 1);
}
int left = 0, right = 0;
int count = map.size();
while (right < s2.length()) {
char curt = s2.charAt(right);
if (map.containsKey(curt)) {
map.put(curt, map.get(curt) - 1);
if (map.get(curt) == 0) {
count--;
}
}
while (count == 0) {
char leftChar = s2.charAt(left);
if (map.containsKey(leftChar)) {
map.put(leftChar, map.get(leftChar) + 1);
if (map.get(leftChar) > 0) {
count++;
}
}
if (right - left + 1 == s1.length()) {
return true;
}
left++;
}
right++;
}
return false;
}
}