checkInclusion.java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[] s1Freq = new int[26];
        int[] s2Freq = new int[26];
        for (int i = 0; i < n; i += 1) {
            s1Freq[s1.charAt(i) - 'a'] += 1;
        }

        int sameCnt = 0;
        // calculate how many characters have same frequencies between s1Freq and s2Freq. When they all match (26), we found a permutation.
        for (int i = 0; i < 26; i += 1) {
            if (s1Freq[i] == s2Freq[i]) {
                sameCnt += 1;
            }
        }

        char c;
        for (int i = 0; i < m; i++) {
            c = s2.charAt(i);
            // if the frequency of c in s1Freq and s2Freq are already same, we're getting one char farther.
            if (s1Freq[c - 'a'] == s2Freq[c - 'a']) {
                sameCnt -= 1;
            }
            s2Freq[c - 'a'] += 1;
            // if the frequency of c in s1Freq and s2Freq are same now, then we're getting one char closer.
            if (s1Freq[c - 'a'] == s2Freq[c- 'a']) {
                sameCnt += 1;
            }

            if (i - n >= 0) {
                c = s2.charAt(i - n);
                // if the frequency of c in s1Freq and s2Freq are already same, we're getting one char farther.
                if (s1Freq[c - 'a'] == s2Freq[c - 'a']) {
                    sameCnt -= 1;
                }
                s2Freq[c - 'a'] -= 1;
                // if the frequency of c in s1Freq and s2Freq are same now, then we're getting one char closer.
                if (s1Freq[c - 'a'] == s2Freq[c- 'a']) {
                    sameCnt += 1;
                }
            }

            if (sameCnt == 26) {
                return true;
            }
        }
        return false;
    }
}