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.
For example:
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").
public class PermutationInString {
public static void main(String[] args) {
boolean bool = checkInclusion();
System.out.println(bool);
}
private static boolean checkInclusion(){
String str1 = "eidbaooo";
String str2 = "ab";
Map<Character, Integer> map2 = new HashMap<>();
for(int i = 0;i<str2.length();i++){
char ch = str2.charAt(i);
map2.put(ch,map2.getOrDefault(ch,0)+1);
}
Map<Character, Integer> map1 = new HashMap<>();
int i = -1;
int j=-1;
int desireCount = str2.length();
int mCount = 0;
boolean resultFlag= false;
while (true){
boolean f1 = false,f2 = false;
while (i<str1.length()-1 && mCount<desireCount){
f1= true;
i++;
char ch = str1.charAt(i);
map1.put(ch,map1.getOrDefault(ch,0)+1);
if(map1.getOrDefault(ch,0)<=map2.getOrDefault(ch,0)){
mCount++;
}
if(mCount==desireCount){
break;
}
}
while (j<i && mCount==desireCount){
f2 = true;
j++;
if(i+1-j==desireCount){ //check if size of string is same as desired count
//System.out.println("result");
resultFlag = true;
break;
}
char ch = str1.charAt(j);
Integer val =map1.get(ch);
if(val>1){
map1.put(ch,map1.get(ch)-1);
}else{
map1.remove(ch);
}
if(map1.getOrDefault(ch,0)<map2.getOrDefault(ch,0)){
mCount--;
}
if(mCount<desireCount){
break;
}
}
if(resultFlag){
System.out.println("result found");
break;
}
if(!f1 && !f2){
System.out.println("result not found");
break;
}
}
if(resultFlag){
//System.out.println("result found");
return true;
}else{
//System.out.println("not found");
return false;
}
// return true;
}
}
No comments:
Post a Comment