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

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay