567. Permutation in String

 一刷 06/2022

Version #1 Sliding Window

(start, end] ensures that the count of all characters is always larger than or equals to zero

Time O(N)

Space O(26) ~ O(1)

Runtime: 8 ms, faster than 68.82% of Java online submissions for Permutation in String.

Memory Usage: 43.5 MB, less than 46.82% of Java online submissions for Permutation in String.

class Solution {

    public boolean checkInclusion(String s1, String s2) {

        int[] count = new int[26];

        for (int i = 0; i < s1.length(); i++) {

            count[s1.charAt(i) - 'a']++;

        }

        int total = s1.length();

        int start = -1;

        // substring (start, end]

        for (int end = 0; end < s2.length(); end++) {

            int eIndex = s2.charAt(end) - 'a';

            count[eIndex]--;

            if (count[eIndex] >= 0) {

                total--;

            }

            while (count[eIndex] < 0) {

                start++;

                int sIndex = s2.charAt(start) - 'a';

                count[sIndex]++;

                if (count[sIndex] > 0) {

                    total++;

                }

            }

            if (total == 0) {

                return true;

            }

        }

        return false;

    }

}