1. Description

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.

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

2. Runtime Distribution

3. Submission Details

4. Example

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

5. Code

public boolean checkInclusion(String s1, String s2) {

    if (s1 == null || s1 == null || s1.length() > s2.length()) {
        return false;
    }

    if (s1.length() == 0) {
        return true;
    }

    Map<Character, Integer> map = new HashMap<Character, Integer>();

    for (int i = 0; i < s1.length(); i++) {
        char c = s1.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
    }

    int count0 = 0;
    int j = 0;
    for (int i = 0; i < s2.length(); i++) {
        char c = s2.charAt(i);
        if (map.containsKey(c)) {
            int pre = map.get(c);
            if (pre == 0) {
                count0--;
            } else if (pre == 1) {
                count0++;
            }
            map.put(c, pre - 1);
        }
        if (i >= s1.length()) {
            c = s2.charAt(j);
            if (map.containsKey(c)) {
                int pre = map.get(c);
                if (pre == 0) {
                    count0--;
                } else if (pre == -1) {
                    count0++;
                }
                map.put(c, pre + 1);
            }
            j++;
        }
        if (count0 == map.size()) {
            return true;
        }
    }
    if (count0 == map.size()) {
        return true;
    }
    return false;
}

6.Test

import java.util.HashMap;
import java.util.Map;

public class LeetCode0567 {
    public boolean checkInclusion(String s1, String s2) {

        if (s1 == null || s1 == null || s1.length() > s2.length()) {
            return false;
        }

        if (s1.length() == 0) {
            return true;
        }

        Map<Character, Integer> map = new HashMap<Character, Integer>();

        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int count0 = 0;
        int j = 0;
        for (int i = 0; i < s2.length(); i++) {
            char c = s2.charAt(i);
            if (map.containsKey(c)) {
                int pre = map.get(c);
                if (pre == 0) {
                    count0--;
                } else if (pre == 1) {
                    count0++;
                }
                map.put(c, pre - 1);
            }
            if (i >= s1.length()) {
                c = s2.charAt(j);
                if (map.containsKey(c)) {
                    int pre = map.get(c);
                    if (pre == 0) {
                        count0--;
                    } else if (pre == -1) {
                        count0++;
                    }
                    map.put(c, pre + 1);
                }
                j++;
            }
            if (count0 == map.size()) {
                return true;
            }
        }
        if (count0 == map.size()) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        LeetCode0567 leetcode = new LeetCode0567();
        System.out.println(leetcode.checkInclusion("abcdxabcde", "abcdeabcdx"));
    }
}