Sliding Window | 17ms | Short | O(n) | Java solution with comments


  • 0
    N

    // This is an O(n) solution, which basically finds all substrings of s
    // which contain all characters of p, and if such a substring happens to
    // be of the same length as p, it adds its starting index to the list

    public List<Integer> findAnagrams(String s, Stringp) {
        List<Integer> list = new ArrayList<Integer>(); 
        if(s == null || p == null || s.length() == 0 || p.length() == 0 || p.length() > s.length())     
           return list; 
        int[] Map = new int[256];
        int start=0, end=0, count=p.length(); 
        for(int i=0; i<=p.length()-1; i++){
            Map[p.charAt(i)]++;
        }
    
        while(end <= s.length()-1) {
            // If a character in p is found in s
            if(Map[s.charAt(end++)]-- > 0) {  
                count--; 
            }
            // This condition is true when a substring in s 
            // is found which has all character in p    
            while(count == 0) {
                // Check if the substring has the same length as p
                if(end - start == p.length()) {
                    list.add(start); 
                }
                // Remove unnecessary characters from starting
                if(Map[s.charAt(start++)]++ == 0) { count++; }  
            }
        }
        return list; 
    }

Log in to reply
 

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