class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character, Integer> s1_map = new HashMap<>();
HashMap<Character, Integer> s2_map = new HashMap<>();
int s1_len = s1.length();
int s2_len = s2.length();
for(int i=0;i<s1_len;i++) {
s1_map.put(s1.charAt(i), s1_map.getOrDefault(s1.charAt(i),0) +1);
}
int i=0;
int j=0;
while(j<s2_len) {
if(j-i+1 <= s1_len) {
s2_map.put(s2.charAt(j), s2_map.getOrDefault(s2.charAt(j),0) +1);
}
if(j-i+1 == s1_len) {
if(isPermutation(s1_map, s2_map)) {
return true;
}
s2_map.put(s2.charAt(i), s2_map.get(s2.charAt(i)) -1);
if(s2_map.get(s2.charAt(i)) == 0) s2_map.remove(s2.charAt(i));
i++;
}
j++;
}
return false;
}
public boolean isPermutation(HashMap<Character, Integer> s1_map, HashMap<Character, Integer> s2_map) {
for(Character c : s2_map.keySet()) {
if( s1_map.get(c) != s2_map.get(c)) {
return false;
}
}
return true;
}}
The above code is the solution of LeetCode 567. Permutation in String. I used the sliding window technique to compare frequencies of the s1 in s2 using HapMap for both strings. The code is working for smaller inputs like
Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains one permutation of s1 ("ba").
but it is failing for the large input like this
But the strange thing is when we typecast s1_map.get(c) to (int)s1_map.get(c) and s2_map.get(c) to (int)s2_map.get(c) see below code for ref, the code is working fine for large inputs. Can anybody explain this strange behavior of hashmap?
public boolean isPermutation(HashMap<Character, Integer> s1_map, HashMap<Character, Integer> s2_map) {
for(Character c : s2_map.keySet()) {
if( (int)s1_map.get(c) != (int)s2_map.get(c)) {
return false;
}
}
return true;
}