Problem
TC:O(n)
SC:(k) is no. of substrings(anagrams) + O(1) for using constant space array of size 26
class Solution { public List<Integer> findAnagrams(String s, String p) { Map<Character,Integer> map = new HashMap<>(); int arrp[] = new int[26]; for(int i = 0;i<p.length();i++) arrp[p.charAt(i)-'a']++; int arrs[] = new int[26]; List<Integer> result = new ArrayList<>(); int left =0,right = 0; while(right<s.length()){ if(right-left+1< p.length()){ arrs[s.charAt(right)-'a']++; right++; } else{ arrs[s.charAt(right)-'a']++; right++; if(check(arrp,arrs)) result.add(left); arrs[s.charAt(left)-'a']--; left++; } } return result; } public boolean check(int a[], int b[]){ for(int i =0;i<26;i++){ if(a[i]!=b[i]) return false; } return true; } }
Top comments (0)