This is a code for finding anagrams in string. How can I optimise further as its giving me TLE error-CodePudding

LeetCode Q:https://leetcode.com/problems/find-all-anagrams-in-a-string/

I believe what I have done is perfectly fine. However, it's giving me a TLE error. What changes do I have to do in order to run this program?

class Solution {
public List<Integer> findAnagrams(String s, String p) {
    int[] fors=new int[26];
    int[] forp=new int[26];
    for(int i=0;i<p.length();i  ){
        forp[p.charAt(i)-'a']  ;
    }
    int k=p.length();
    int len=s.length();
    int i=0;
    int j=0;
    ArrayList<Integer> list=new ArrayList<>();
    if(s.length()<p.length()) return list;
    while(j<len){
        fors[s.charAt(j)-'a']  ;
        if(j-i 1<k)j  ;
        if(j-i 1==k){
            if(areSame(fors,forp)){
                list.add(j-k 1);
                fors[s.charAt(i)-'a']--;
                i  ;
                j  ;
            }
        }   
    }
    return list;   
}
public boolean areSame(int[] countS, int[] countP){
for(int i=0;i<26;i  ){
    if(countS[i]!=countP[i]){
        return false;
    }
}
return true;
}

}

CodePudding user response：

I see 2 issues with your code. First, regarding TLE, you have an infinite loop because you iterate j and i only if the windows are equal.

if(areSame(fors,forp)){     
    list.add(j-k 1);        
    fors[s.charAt(i)-'a']--;        
    i  ;        
    j  ;        
}

You should iterate i regardless. Fixing this is as simple as moving the iteration out of the if case.

if(areSame(fors,forp)){
    list.add(j- p.length()  1);
}
fors[s.charAt(i)-'a']--;
i  ;

Notice that I also move out the S - counter so that you keep moving even if the areSame checker is false.

The second issue is how you iterate j. By incrementing j before the areSame check, you check the windows 1 size too early. You can fix this by moving the j iteration to the end :)

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        
        int[] fors=new int[26];
        int[] forp=new int[26];
        for(int i=0;i<p.length();i  ){
            forp[p.charAt(i)-'a']  ;
        }
        
        int i=0;
        int j=0;
        ArrayList<Integer> list=new ArrayList<>();
        if(s.length()<p.length()) return list;
        while(j<s.length()){
            fors[s.charAt(j)-'a']  ;

            if(j-i 1== p.length()){
                if(areSame(fors,forp)){
                    list.add(j- p.length()  1);
                }
                fors[s.charAt(i)-'a']--;
                i  ;
            }
            j  ;
        }
        return list;   
    }
    public boolean areSame(int[] countS, int[] countP){
        for(int i=0;i<26;i  ){
            if(countS[i]!=countP[i]){
                return false;
            }
        }
        return true;
    }
}