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; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter