DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Find all anagrams in the string[Fixed Window pattern]

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)