567. Permutation in String

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        int[] targetCountMap = new int[26];
        int targetDistinctCharCount = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (targetCountMap[s1.charAt(i) - 'a']++ == 0) {
                targetDistinctCharCount++;
            }
        }

        int[] windowCountMap = new int[26];
        int distinctCharCount = 0;
        int i = 0;
        for (int j = 0; j < s2.length(); j++) {
            int offset = s2.charAt(j) - 'a';
            if (++windowCountMap[offset] == targetCountMap[offset]) {
                distinctCharCount++;
            }

            while (distinctCharCount == targetDistinctCharCount) {
                // 当不同的字符数已经匹配时，说明窗口字符串长度大于等于目标字符串长度，此时检查字符串长度是否相同
                if (j - i + 1 == s1.length()) {
                    return true;
                }

                // 尝试缩小窗口
                int leftmostOffset = s2.charAt(i++) - 'a';
                if (windowCountMap[leftmostOffset]-- == targetCountMap[leftmostOffset]) {
                    distinctCharCount--;
                }
            }
        }

        return false;
    }
}

注意此题要求窗口字符串长度与目标字符串长度相等。

Reference

567. Permutation in String
剑指 Offer II 014. 字符串中的变位词