17ms Java sliding window


  • 19
    D
    public List<Integer> findAnagrams(String s, String p) {
        int[] chars = new int[26];
        List<Integer> result = new ArrayList<>();
    
        if (s == null || p == null || s.length() < p.length())
            return result;
        for (char c : p.toCharArray())
            chars[c-'a']++;
    
        int start = 0, end = 0, count = p.length();
        // Go over the string
        while (end < s.length()) {
            // If the char at start appeared in p, we increase count
            if (end - start == p.length() && chars[s.charAt(start++)-'a']++ >= 0)
                count++;
            // If the char at end appeared in p (since it's not -1 after decreasing), we decrease count
            if (--chars[s.charAt(end++)-'a'] >= 0)
                count--;
            if (count == 0)
                result.add(start);
        }
        
        return result;
    }

  • 16
    L

    Nice! I've built on it with some comments along the way to help my own comprehension of the problem. Maybe someone else will find it helpful as well.

    public List<Integer> findAnagrams(String s, String p) {
            List<Integer> ans = new ArrayList<>();
            if (p.length() > s.length()){
                return ans;
            }
            int[] charCounts = new int[26];
            for (char c : p.toCharArray()){
                charCounts[toInt(c)]++;
            }
            
            // Note: in the next iteration of this solution we may be able to move this
            // into the while loop, but this does help my understanding of the solution
            int left = 0; int right = 0; int numDiff = p.length();
            for (right = 0; right < p.length(); right++){
                char c = s.charAt(right);
                if (charCounts[toInt(c)] > 0){
                    numDiff--;
                }
                charCounts[toInt(c)]--;
            }
            if (numDiff == 0){
                ans.add(0);
            }
            
            // At this point what does the 'charCounts' represent?
            // positive numbers represent the needed number of occurances of a given
            // character that are needed to form an anagram.
            // negative numbers represent number of occurances of a character which is not 
            // part of the anagram OR extra occurances of a character which IS part of the anagram. 
            // Important note: a charCounts which contains all zero counts represents a state of 
            // the anagram's existence. 
            while (right < s.length()){
                char leftChar = s.charAt(left++);
                if (charCounts[toInt(leftChar)] >= 0){
                    // the character we're moving away from is part of the anagram
                    // therefore we need to add to the difference
                    numDiff++;
                }
                charCounts[toInt(leftChar)]++; // record occurance of character whether of not it's part of the anagram
            
                char rightChar = s.charAt(right++);
                charCounts[toInt(rightChar)]--;
                // the really interesting part, we end up with negatives in charCounts in two following two cases
                // 1. if the character is not in the anagram
                // 2. if a character IS in the anagram but we don't need any more of it
                if (charCounts[toInt(rightChar)] >= 0){
                    // remember that if by subtracting the count at the right edge the result is 0 or more, it means
                    // we have found a character which belongs in the anagram
                    numDiff--;
                }
                
                if (numDiff == 0){
                    ans.add(left);
                }
                
            }
            
            return ans;
        }
        
        private int toInt(char c){
            return c - 'a';
        }
    

  • 0
    I

    Best solution ever!


  • 0
    C

    Please try this test case:
    s: "bpaa"
    p: "aa"

    Expect result:{2}


  • 0
    D

    @c.tianyi1989

    I've updated the code. The fix is to change == to >= in both if conditions.

    Thanks for finding the bug!


  • 0

    @c.tianyi1989 Thanks, I have added your test case.


  • 0
    G

    Nice solution @dahui.

    Slightly modified code here

    • Fixed size sliding window moves at every step
    • start ptr decrement the character in position and end ptr increments it.
    • Initialize count to the size of p; decrement count when the charachter's count is positive (count of characters in p are incremented initially) when visited by start ptr and increment count during end ptr if the value is positive.
    • When the sliding window has a valid boundary (end > -1 && start < s.length) and count == 0 indicates a successful match
     public List<Integer> findAnagrams(String s, String p) {
            List<Integer> result = new ArrayList<Integer>();
            if(s == null || p == null || s.length() < p.length() || p.isEmpty()) return result;
    
            char[] alphabets = new char[26];
            for(char c : p.toCharArray()) alphabets[c-97]++;
    
            int start = 0,  count = p.length(), end = 1 - count ;
            char[] stream = s.toCharArray();
            while(start < s.length()) {
    
                if(alphabets[stream[start]-97] > 0) count--;
    
                alphabets[stream[start]-97]--;
    
                if(end > -1) {
                    if(count == 0) {
                        result.add(end);
                    }
                    alphabets[stream[end]-97]++;
                    if(alphabets[stream[end]-97] > 0) count++;
                }
    
    
                start++;
                end++;
            }
    
            return result;
        }
    

  • 0

    @lemeore
    Thank you for making such detailed comments!
    I have one question:

    for (right = 0; right < p.length(); right++){
        char c = s.charAt(right);
        if (charCounts[toInt(c)] > 0){
             numDiff--;
        }
        charCounts[toInt(c)]--;
    }
    if (numDiff == 0){
        ans.add(0);
    }
    

    I dont quite understand why you have this part of codes: Are you simply adding this part to deal with the corner case to help you better understanding the problem?
    Thank you for your answer.


  • 0
    D

    @传说选手 This part was for initialization of the window, i.e. maintain a window of size p.length(), which could make the logic in the while loop clearer.

    To shorten the code, I've added this part into the while loop.


  • 0
    B

    @lemeore said in 17ms Java sliding window:

    charCounts[toInt(leftChar)]++; // record occurance of character whether of not it's part of the anagram

    Thank you very much for the explanation. Only this line I don't understand:
    charCounts[toInt(leftChar)]++; // record occurance of character whether of not it's part of the anagram
    Can you tell me why we should record the occurrence of the leftChar regardless of its existence in the anagram? What if we don't include it? How did you come up with this idea?
    Thanks a lot!


Log in to reply
 

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