Java O(n) / beats 94.5% solutions


  • 0
    A
    public List<Integer> findAnagrams(String s, String p) {
            int[] count = new int[26];
            List<Integer> result = new ArrayList<Integer>();
            if(s == null || p == null){
                return result;
            }
            for(int i = 0; i < p.length(); i++){
                int x = (int) p.charAt(i) - 'a';
                count[x]++;
            }
            for(int i = 0; i < s.length(); i++){
                // add back character beyond the scope of what is being considered
                if(i >= p.length()){
                    int x = (int) s.charAt(i - p.length()) - 'a';
                    count[x]++;
                }
                
                int c = s.charAt(i) - 'a';
                count[c]--;
                if(i >= p.length() - 1){
                    boolean flag = true;
                    
                    for(int j = 0; j < 26; j++){
                        if(count[j] < 0){
                            flag = false;
                            break;
                        }
                    }
                    
                    if(flag){
                        result.add(i - p.length() + 1);
                    }
                }
            }
            
            return result;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.