Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Getting TEL for below code. What's wrong with my code?

import java.util.*;
    public class FindAllAnagramsInAString_438{
        public static void main(String[] args){
            String s="abab";
            String p="ab";
            // String s="cbaebabacd";
            // String p="abc";
            System.out.println(findAnagrams(s,p));
        }
        public static List<Integer> findAnagrams(String s, String p) {
            int i=0;
            int j=p.length();
            List<Integer> list=new ArrayList<>();
            while(j<=s.length()){
                //System.out.println("Substring >>" s.substring(i,j));
                if(isAnamgram(s.substring(i,j),p)){
                    list.add(i);
                }
                i  ;
                j  ;
            }
            return list;
        }
        public static boolean isAnamgram(String s,String p){
            HashMap<Character,Integer> map=new HashMap<>();
            if(s.length()!=p.length()) return false;
            for(int i=0;i<s.length();i  ){
                char chs=s.charAt(i);
                char chp=p.charAt(i);
                map.put(chs,map.getOrDefault(chs,0) 1);
                map.put(chp,map.getOrDefault(chp,0)-1);
            }
            for(int val:map.values()){
                if(val!=0) return false;
            }
            return true;
        }
    }

CodePudding user response：

You shouldn't be creating a whole new frequency table for each substring. Given a table for index i, the table for index i 1 changes by only 2 counts. Just modify the previous table to get the next one. Also don't bother counting characters that don't appear in the search string.

Also, don't do the whole table comparison -- just keep track of the number of mismatched counts. Again this changes by at most 2 counts per index.

Finally, don't allocate a new substring for each index.

CodePudding user response：

Looks good now

HashMap<Character,Integer> pMap=new HashMap<>();
        HashMap<Character,Integer> sMap=new HashMap<>();
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<p.length();i  ){
            char ch=p.charAt(i);
            pMap.put(ch,pMap.getOrDefault(ch,0) 1);
        }
        int j=0;
        while(j<p.length()){
            char ch=s.charAt(j);
            sMap.put(ch,sMap.getOrDefault(ch,0) 1);
            j  ;
        }
        int i=0;
        while(j<s.length()){
            if(pMap.equals(sMap)){
                list.add(i);
            }
            sMap.put(s.charAt(j),sMap.getOrDefault(s.charAt(j),0) 1);
            if((sMap.getOrDefault(s.charAt(i),0)-1)==0){
                sMap.remove(s.charAt(i));
            }else{
                sMap.put(s.charAt(i),sMap.getOrDefault(s.charAt(i),0)-1);
            }
            i  ;
            j  ;
        }
        return list;