Shortest/Concise JAVA O(n) Sliding Window Solution


  • 102

    Same idea from a fantastic sliding window template, please refer:
    https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

    Time Complexity will be O(n) because the "start" and "end" points will only move from left to right once.

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;
        int[] hash = new int[256]; //character hash
        //record each character in p to hash
        for (char c : p.toCharArray()) {
            hash[c]++;
        }
        //two points, initialize count to p's length
        int left = 0, right = 0, count = p.length();
        while (right < s.length()) {
            //move right everytime, if the character exists in p's hash, decrease the count
            //current hash value >= 1 means the character is existing in p
            if (hash[s.charAt(right++)]-- >= 1) count--; 
            
            //when the count is down to 0, means we found the right anagram
            //then add window's left to result list
            if (count == 0) list.add(left);
        
            //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window
            //++ to reset the hash because we kicked out the left
            //only increase the count if the character is in p
            //the count >= 0 indicate it was original in the hash, cuz it won't go below 0
            if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;
        }
        return list;
    }

  • 21
    T

    My understanding of the solution -- Basically, we are interested only when every hash[i] becomes 0. There are a number of ways of doing it. To understand OP's approach, we observe that:

    • the sum of all hash[i] is always >=0;
    • count is the sum of all positive hash[i];
    • therefore, every hash[i] is zero if and only if count is 0.

    The genius of this approach is that the code is shorter, compared to our instinctive approach of maintaining the count of hash[i]==0. Though, It is a little roundabout for comprehension :)


  • 219
    K

    Very nice solution and reference, but I really dont like this style "if (hash[s.charAt(right++)]-- >= 1) count--; "
    So just re-phrase your code

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> list = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;
        
        int[] hash = new int[256]; //character hash
        
        //record each character in p to hash
        for (char c : p.toCharArray()) {
            hash[c]++;
        }
        //two points, initialize count to p's length
        int left = 0, right = 0, count = p.length();
        
        while (right < s.length()) {
            //move right everytime, if the character exists in p's hash, decrease the count
            //current hash value >= 1 means the character is existing in p
            if (hash[s.charAt(right)] >= 1) {
                count--;
            }
            hash[s.charAt(right)]--;
            right++;
            
            //when the count is down to 0, means we found the right anagram
            //then add window's left to result list
            if (count == 0) {
                list.add(left);
            }
            //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window
            //++ to reset the hash because we kicked out the left
            //only increase the count if the character is in p
            //the count >= 0 indicate it was original in the hash, cuz it won't go below 0
            if (right - left == p.length() ) {
               
                if (hash[s.charAt(left)] >= 0) {
                    count++;
                }
                hash[s.charAt(left)]++;
                left++;
            
            }
    
            
        }
            return list;
        }
    }
    

  • 2

    Can anyone give me a hint why it's 256? Since the "biggest" character is 'z', which is 122. I don't know why the original post use 128 either.

    Can I just use 123? Or there is something important I missed?

    Thanks in advance!


  • 5

    @zhugejunwei

    You are right,
    we can use int[128] instead of int[256].
    I was thinking about extended ascii ( 0 ~ 256), but it doesn't apply to this problem.

    actually for this specific case, if we are given all lower case alphabets.
    int[26] is enough.
    Just do hash[c - 'a'] every time.


  • 8

    @zhugejunwei 128 or 256 is just for people too lazy/smart to look for a tighter bound :-)


  • 0

    @StefanPochmann hahah, you got my lazy point.


  • 6
    L

    @zhugejunwei I guess the thought process sort of went like this.

    Hmmm, need to convert a char to int, 256 is good..
    Oh, wait. only lower case letters, 26 is sufficient but don't want to type - 'a'
    Well, could find out what 'z' is and use that, but probably not worth the effort
    Yeah, 256 is good...

    The same goes for 128, except the other author probably roughly knows 'z' is just over 100


  • 1

    @lx223 That's at least exactly how it works for me :-). Except for 128 I don't think 'z' is just over 100 but that 'z' is ASCII (and that ASCII only has 128 characters).


  • 0

    @lx223 Thanks for your interesting explanation... haha


  • 1

    @zhugejunwei That is the total number of ASCII. Which I think [26] is enough. The question says only lower case letter.


  • 0
    S

    I still can't understand why this work....what‘s the meaning of "hash[c]++"?


  • 0
    S

    @Skyfacon
    I not understood the code can anyone please tell about how sliding window protocol works please


  • 3
    C

    @Skyfacon it means initialize the hash[] array we just build, for instance, hash['a'] ++, it means, in the hash[97] the value now is 1, use this we can map all the character in the string p into hash[] array, we mark every character in p string down into the hash[] array, then we can manipulate this hash[] array, see if the value in the hash[] array is not 0, then we may consider it match one character of p string, for instance, if the s string have the same character 'a', we can check whether the value of hash[s.charAt('a')] not equal to 0, if the value is not equal to 0 , then we can say we find one character match.,we make sure counter--(the initial counter value is p.length). And so on and so forth, we check every character in string p, until counter equal to 0. Then we find one pattern is matched. And we add it to the list. Hope it helps.


  • 0
    C

    @sunnysoni26 Hi sunny, you can consider the sliding windows method like this, every time while we are doing the check process, left bar is fixed, only right bar is shifted to check the right match anagrams, when this time check is finished, then fixed left bar is move right one step, and the right bar back to its origin place and then move one step to right, then we can start the same process again until the right - left is not equal to the length of the string p.


  • 0
    S

    can someone please explain the precedence of hash[s.charAt(right++)]-- >= 1


  • 0
    M

    Do we need to initialize the array? I mean hash[];


  • 0
    C

    @SC30 it means if hash[s.charAt(right)] >=1 then right++ and hash[s.charAt(right)]--


  • 1

    @Madaozuishuaile
    nope, hash[] is initialized as all hash[i] = 0
    and it is a counter for every character in the string p


  • 1
    N

    Thanks!!!!!!!!!!!!!!!!!!!!!!!!!!
    Wonderful Solution!!!!!!!!!!!!!!!!!!!!!!!!!!!
    A little improvement

    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> list = new ArrayList<Integer>();
            if(s == null || p == null || s.length() < p.length())   return list;
            int lengthp = p.length();
            int lengths = s.length();
            int[] hash = new int[26];
            for(int i = 0; i < lengthp; i ++){
                ++hash[p.charAt(i) - 97];
            }
            int left = 0, right = 0;
            while(right < lengths){
                if(hash[s.charAt(right++) - 97]-- > 0) lengthp--;
                if(lengthp == 0)    list.add(left);
                if(right - left == p.length() && hash[s.charAt(left++) - 97]++ >= 0)    lengthp++;
            }
            return list;
        }
    }
    

Log in to reply
 

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