Java sliding window solution


  • 0
    S
        public boolean checkInclusion(String s1, String s2) {
            int i, len1 = s1.length(), len2 = s2.length();
            if (len1 > len2)
                return false;
            
            int[] charCount = new int[26];
            int diffN = len1, diffP = 0, index, index2;
            for (i=0;i<len1;i++) {
                index = s1.charAt(i) - 'a';
                charCount[index]--;
            }
            for (i=0;i<len1;i++) {
                index = s2.charAt(i) - 'a';
                charCount[index]++;
                if (charCount[index] <= 0) {
                    diffN--;
                } else {
                    diffP++;
                }
            }
            if (diffN == 0 && diffP == 0)
                return true;
    
            for (i=len1;i<len2;i++) {
                index = s2.charAt(i) - 'a';
                index2 = s2.charAt(i-len1) - 'a';
                if (index == index2)
                    continue;
                charCount[index]++;
                charCount[index2]--;
    
                if (charCount[index] <= 0)
                    diffN--;
                else
                    diffP++;
                
                if (charCount[index2] >= 0)
                    diffP--;
                else
                    diffN++;
                if (diffN == 0 && diffP == 0)
                    return true;
            }
            return false;
        }
    }

Log in to reply
 

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