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

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

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 map = new HashMap();

	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;
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

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 map = new HashMap();

		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"));
	}
}

[/restab]
[/restabs]