Q20 Find All Anagrams in a String - LeetCode
Thu Jan 26 2023 06:36:19 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public List<Integer> findAnagrams(String s, String p) {
//baseCase
if(p.length() > s.length())
return new ArrayList<>();
//make HM of p
HashMap<Character , Integer> small = new HashMap<>(); //for string p
for(int i =0 ; i< p.length();i++){
char ch = p.charAt(i);
small.put(ch , small.getOrDefault(ch,0)+1);
}
ArrayList<Integer> ans = new ArrayList<>();
HashMap<Character,Integer> big = new HashMap<>(); //for string s
//adding first p.length() chars in big
for(int i =0 ; i< p.length();i++){
char ch = s.charAt(i);
big.put(ch , big.getOrDefault(ch,0)+1);
}
//now j will be at p.length() and i will be at 0 //or j - p.length()
int j = p.length();
while(j < s.length()){
//first check if maps are equal
if(big.equals(small))
ans.add(j - p.length());
//slide the window by adding and removing a character
//add character
char ch = s.charAt(j);
big.put(ch , big.getOrDefault(ch,0)+1);
//remove last character
ch = s.charAt(j - p.length());
if(big.get(ch)==1)
big.remove(ch);
else
big.put(ch , big.get(ch)-1);
j++;
}
//checking the last window
if(big.equals(small))
ans.add(j - p.length());
return ans;
}
}
content_copyCOPY
https://leetcode.com/problems/find-all-anagrams-in-a-string/
Comments