Java Solution, Sliding Window


  • 47
    1. How do we know string p is a permutation of string s? Easy, each character in p is in s too. So we can abstract all permutation strings of s to a map (Character -> Count). i.e. abba -> {a:2, b:2}. Since there are only 26 lower case letters in this problem, we can just use an array to represent the map.
    2. How do we know string s2 contains a permutation of s1? We just need to create a sliding window with length of s1, move from beginning to the end of s2. When a character moves in from right of the window, we subtract 1 to that character count from the map. When a character moves out from left of the window, we add 1 to that character count. So once we see all zeros in the map, meaning equal numbers of every characters between s1 and the substring in the sliding window, we know the answer is true.
    public class Solution {
        public boolean checkInclusion(String s1, String s2) {
            int len1 = s1.length(), len2 = s2.length();
            if (len1 > len2) return false;
            
            int[] count = new int[26];
            for (int i = 0; i < len1; i++) {
                count[s1.charAt(i) - 'a']++;
                count[s2.charAt(i) - 'a']--;
            }
            if (allZero(count)) return true;
            
            for (int i = len1; i < len2; i++) {
                count[s2.charAt(i) - 'a']--;
                count[s2.charAt(i - len1) - 'a']++;
                if (allZero(count)) return true;
            }
            
            return false;
        }
        
        private boolean allZero(int[] count) {
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) return false;
            }
            return true;
        }
    }
    

  • 0
    J

    awesome solution ,thank you for share it.


  • 8

    Nice!
    Modified it a little bit.

    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) return false;
        
        int[] count = new int[26];
        for (int i = 0; i < len1; i++) {
            count[s1.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < len2; i++) {
            count[s2.charAt(i) - 'a']--;
            if(i - len1 >= 0) count[s2.charAt(i - len1) - 'a']++;
            if (allZero(count)) return true;
        }
        
        return false;
    }
    
    private boolean allZero(int[] count) {
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) return false;
        }
        return true;
    }

  • 0
    S

    Can u explain the logic?? I cant understand what logic u are using here..


  • 0

    @Seenivas Added some explanation. Hope that help.


  • 1
    A

    My C++ version with a change in the last loop.

    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {        
            int len1 = s1.length(), len2 = s2.length();
            if (len1 > len2) return false;
        
            vector<int> count(26, 0);
            for (int i=0; i<len1; ++i) {
                count[s1[i]-'a']++;
                count[s2[i]-'a']--;
            }
    
            int numZeroes = 0;
            for (int i=0; i<26; ++i) {
                if (count[i] == 0)
                    numZeroes++;
            }
            if (numZeroes == 26) return true;
        
            for (int i=len1; i<len2; ++i) {
                count[s2[i]-'a']--;
                if (count[s2[i]-'a'] == 0)
                    numZeroes++;
                else if (count[s2[i]-'a'] == -1)
                    numZeroes--;
    
                count[s2[i-len1]-'a']++;                        
                if (count[s2[i-len1]-'a'] == 0)
                    numZeroes++;
                else if (count[s2[i-len1]-'a'] == 1)
                    numZeroes--;
    
                if (numZeroes == 26) return true;
            }
            return false;
        }
    };

  • 2
    Y

    A slight difference in my code is it doesn't check 26 times in each loop.

    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s1.toCharArray()) {
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        }
    
        int matchedCnt = 0;
        for (int i = 0; i < s2.length(); ++i) {
            char c = s2.charAt(i);
            if (cnt.containsKey(c)) {
                cnt.put(c, cnt.get(c) - 1);
                if (cnt.get(c) == 0) {
                    matchedCnt++;
                }
            }
            if (i >= s1.length()) {
                c = s2.charAt(i - s1.length());
                if (cnt.containsKey(c)) {
                    if (cnt.get(c) == 0) {
                        matchedCnt--;
                    }
                    cnt.put(c, cnt.get(c) + 1);
                }
            }
    
            if (matchedCnt == cnt.keySet().size()) { 
                return true;
            }
        }
        return false;
    }
    

  • 3

    In first loop we assume that s1 and s2 has same length, we use a map, for every char of s1 we add to map, for every char of s2 we delete from map. After that we check if for every char in map, we have a perfect balance.(each char has count zero)

    In second loop we start to move the windows from left to right. Each step we deal with the head and tail of the window, then check if the map has a balance.

        public boolean checkInclusion(String s1, String s2) {
            
          int l1 = s1.length(), l2 = s2.length();
          if(l1 > l2) return false;
    
          int[] map = new int[26];
          char[] s1c = s1.toCharArray(), s2c = s2.toCharArray();
          for(int i = 0; i < l1; i++){
            map[s1c[i] - 'a']++;
            map[s2c[i] - 'a']--;
          }
          
          if(isAllZero(map)) return true;
          
          for(int i = 0; i < l2 - l1; i++){
            map[s2c[i] - 'a']++;
            map[s2c[i + l1] - 'a']--;
            if(isAllZero(map)) return true;
          }
          
          return false;
        }
        
        boolean isAllZero(int[] array){
          for(int a: array){
            if(a > 0) return false;  
          }    
          return true;
        }

  • 2

    @yl I came up with similar idea and made it a bit concise

        public boolean checkInclusion(String s1, String s2) {
            if (s2.length() < s1.length()) return false;
            int hits = 0;
            int[] counts = new int[26];
            for (int i = 0; i < s1.length(); i++) {
                counts[s1.charAt(i)-'a']++;
            }
            for (int i = 0, j = 0; i < s2.length(); i++) {
                if (counts[s2.charAt(i)-'a']-- > 0 && ++hits == s1.length()) return true;
                if (i >= s1.length()-1 && counts[s2.charAt(j++)-'a']++ >= 0) hits--;
            }
            return false;
        }
    

  • 0
    M

    @shawngao said in Java Solution, Sliding Window:

    public class Solution {
    public boolean checkInclusion(String s1, String s2) {
    int len1 = s1.length(), len2 = s2.length();
    if (len1 > len2) return false;

        int[] count = new int[26];
        for (int i = 0; i < len1; i++) {
            count[s1.charAt(i) - 'a']++;
            count[s2.charAt(i) - 'a']--;
        }
        if (allZero(count)) return true;
        
        for (int i = len1; i < len2; i++) {
            count[s2.charAt(i) - 'a']--;
            count[s2.charAt(i - len1) - 'a']++;
            if (allZero(count)) return true;
        }
        
        return false;
    }
    
    private boolean allZero(int[] count) {
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) return false;
        }
        return true;
    }
    

    }

    AllZero still have O(26) complexity. Having another array to count is better


  • 0
    B

    Similar idea with you, but use a variable cnt to store the number of characters matched, then if cnt equals the size of s1, return true. Thus we don't need to check all zeros in map.

    public:
        bool checkInclusion(string s1, string s2) {
            // solution 1, O(n) time O(n) space
            vector<int> cnt_s1(26, 0);
            for(auto c:s1)
                ++cnt_s1[c-'a'];
            
            int cnt = 0;    // number of chars that are matched
            for(int left=0, right=0; right<s2.size(); ++right){
                // check if s2[right] is matched
                if(cnt_s1[s2[right]-'a']>0) ++cnt;  // s2[right] is needed and provided
                --cnt_s1[s2[right]-'a'];
                
                if(right-left+1>s1.size()){
                    // remove s2[left] from the window
                    if(cnt_s1[s2[left]-'a']>=0) --cnt;  // s2[left] is needed but removed
                    ++cnt_s1[s2[left]-'a'];
                    ++left;
                }
                if(cnt==s1.size()) return true;
            }
            
            return false;
        }
    };

  • 0
    M

    I do not understand well.
    for example, s1 = "ab", s2 = "abcdefg", the function returns true after the first loop, but that should not be the correct answer, right?
    can anyone tell me why it works? thank you so much!


  • 0
    B

    @moxianyuan
    "ab" is a permutation of s1, and also a substring of s2, so the result should be true.


  • 0

    Another Approach:

    public boolean checkInclusion(String s1, String s2) {
        int [] map = new int [256];
        for (char ch : s1.toCharArray()) map [ch] ++;
        for (int idx = 0, start = 0; idx < s2.length(); idx ++) {
            char ch = s2.charAt (idx);
            if (-- map [ch] < 0) while (map [ch] != 0) map [s2.charAt (start ++)] ++;
             else if (idx - start + 1 == s1.length()) return true;
        }
        return false;
    }
    

  • 0
    Z

    I tried to use an string of 26 characters to keep track of numbers of each characters.

    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            if(s2.size() < s1.size()) return false;
            string s1sum = "aaaaaaaaaaaaaaaaaaaaaaaaaa";
            string s2sum = "aaaaaaaaaaaaaaaaaaaaaaaaaa";
            for(int i = 0; i < s1.size(); i++){
                s1sum[s1[i]-'a'] = s1sum[s1[i]-'a'] + 1;
                s2sum[s2[i]-'a'] = s2sum[s2[i]-'a'] + 1;
            }
            if(s1sum.compare(s2sum) == 0) return true;
            
            for(int i = 1; i <= s2.size() - s1.size(); i++){
                s2sum[s2[i-1]-'a'] = s2sum[s2[i-1]-'a'] - 1;
                s2sum[s2[i+s1.size()-1]-'a'] = s2sum[s2[i+s1.size()-1]-'a'] + 1;
                if(s1sum.compare(s2sum) == 0) return true;
            }
            return false;
        }
    };
    

  • 0
    W

    what an awesome solution, how can you come up with the sliding window solution my god!


  • 0
    Y

    awesome, same with mine


  • 0

    I think it's similar to a sliding window anagram problem.


Log in to reply
 

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