567 Permutation in String

567. Permutation in String

1. Question

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"

Output: True

Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1= "ab" s2 = "eidboaoo"

Output: False

2. Implementation

(1) Two Pointers + Hash

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

        int[] map = new int[256];

        for (char c : s1.toCharArray()) {
            ++map[c];
        }

        int end = 0, start = 0, count = s1.length();

        while (end < s2.length()) {
            if (map[s2.charAt(end)] > 0) {
                --count;
            }
            --map[s2.charAt(end)];
            ++end;

            if (end - start - 1 == s1.length()) {
                if (map[s2.charAt(start)] >= 0) {
                    ++count;
                }
                ++map[s2.charAt(start)];
                ++start;
            }

            if (count == 0) {
                return true;
            }
        }
        return false;
    }
}

3. Time & Space Complexity

Two Pointers + Hash: 时间复杂度O(n), 空间复杂度O(1)