8 lines slide window solution in Java


  • 30
    T
        public boolean checkInclusion(String s1, String s2) {
            int[] count = new int[128];
            for(int i = 0; i < s1.length(); i++) count[s1.charAt(i)]--;
            for(int l = 0, r = 0; r < s2.length(); r++) {
                if (++count[s2.charAt(r)] > 0)
                    while(--count[s2.charAt(l++)] != 0) { /* do nothing */}
                else if ((r - l + 1) == s1.length()) return true;
            }
            return s1.length() == 0;
        }
    

    Update:

    I gonna use pictures to describe what the above code does. The first "for" loop counts all chars we need to find in a way like digging holes on the ground:

    0_1493821046494_Screen Shot 2017-05-03 at 8.56.24 AM.png
    Blank bars are the holes that we need to fill.

    We scan each one char of the string s2 (by moving index r in above code) and put it in the right hole:
    0_1493821246327_Screen Shot 2017-05-03 at 8.56.46 AM.png
    The blue blocks are chars from s2.

    But if the char in s2 is not in s1, or, the count of the char is more than the count of the same char in s1, we got some thing like this:
    0_1493822441927_Screen Shot 2017-05-03 at 8.57.32 AM.png
    Note the last blue block sticks out of ground. Any time we encounter a sticking out block - meaning a block with value 1 - we stop scanning (that is moving "r"). At this point, there is only one sticking out block.

    Now, we have an invalid substring with either invalid char or invalid number of chars. How to remove the invalid char and continue our scan? We use a left index ("l" in above code) to remove chars in the holes in the same order we filled them into the holes. We stop removing chars until the only sticking out block is fixed - it has a value of 0 after fixing. Then, we continue our scanning by moving right index "r".

    Our target is to get:
    0_1493823560108_Screen Shot 2017-05-03 at 9.02.56 AM.png
    To check if all holes are filled perfectly - no more, no less, all have value of 0 - we just need to make sure (r - l + 1) == s1.length().

    Update 2:
    Thanks to mylemoncake comment. I have updated the last line to : return s1.length() == 0; This takes care of the case s1 is an empty string.


  • 0

    Your solution is so elegant!


  • 0

    while(--count[s2.charAt(l++)] != 0) this code is so cool !!


  • 1
    R

    @fallcreek It has been a while since last time I programed in java, I dont really get 'while(--count[s2.charAt(l++)] != 0) { /* do nothing */}' what this means. Could you plaese shed a light?


  • 0
                while(l <= r){
                    if(--count[s2.charAt(l)] == 0){
                        l++;
                        break;
                    }
                    l++;
                }       
    

    @rujia
    I think this code can be rewrite as above (l <= r will be always true), silde the left window to find valid character, if not l = r+1. hope it will help you :)


  • 0
    M

    Need to consider a corner case of :

    ""
    "eidbaooo"

    Should return true;


  • 0
    M

    Great visualization.


  • 0
    Y

    This solution is awesome, upvoted!


  • 1
    Z

    Great solution! O(n) with small constant factor. I rewrote it in C++.

        bool checkInclusion(string s1, string s2) {
            int count[26] = {};
            for (char c:s1) count[c-'a']--;
            for (int l = 0, r = 0; r < s2.length(); r++) {
                int tmp = s2[r]-'a';
                count[tmp]++;
                if (count[tmp] > 0) {
                    // move left pointer l to reset count[tmp] = 0
                    while (s2[l] != s2[r]) 
                        --count[s2[l++]-'a'];
                    --count[s2[l++]-'a'];
                }
                else if (r-l+1 == s1.size())
                    return true;
            }
            return s1.size() == 0;
        }
    

  • 0
    C

    Great solution.I rewrote in my way.so I can understand easily.

    class Solution {
    public:
    bool checkInclusion(string s1, string s2) {
    vector<int> vec(128,0);
    int begin=0,end=0;
    for(char ch : s1){
    vec[ch]++;
    }
    int count=s1.length();
    while(end<s2.length()){
    vec[s2[end]]--;
    while(vec[s2[end]]<0&&begin<=end){
    vec[s2[begin++]]++;
    }
    if(-begin+end+1==count) return true;
    end++;
    }
    return false;
    }
    };


  • 0
    P

    Same idea, added some comments.

    public class Solution {
        public boolean checkInclusion(String s1, String s2) {
            int[] map = new int[26];
            int sum = s1.length();
            // construct frequency map
            for(int i = 0; i< s1.length(); i++){
                map[s1.charAt(i) - 'a']++;
            }
            for(int r = 0, l = 0; r < s2.length(); r++){
                char c = s2.charAt(r);
                if(map[c - 'a'] > 0){
                    map[c - 'a']--;
                    sum--;
                    //check for permutation match.
                    if(sum == 0) return true;
                }else{
            // if there is enough number for char c or c is never seen before.
            // we move left pointer next to the position where we first saw char c 
            // or to the r+1(we never see char c before), 
            //and during this process we restore the map.
                    while(l<= r && s2.charAt(l) != s2.charAt(r)){
                        map[s2.charAt(l) - 'a'] ++;
                        l++;
                        sum++;
                    }
                    l++;
                }
            }
            return false;
        }
    }
    

  • 0
    K

    @panzw said in 8 lines slide window solution in Java:

    while(l<= r && s2.charAt(l) != s2.charAt(r)){

    I think we should use l < r instead of l < = r, because when l == r , this condition can never be true ( s2.charAt(l) != s2.charAt(r))

    Please correct me.


Log in to reply
 

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