PermutationInString567.java

/**
 * 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
 * 
 * Note:
 * The input strings only contain lower case letters.
 * The length of both given strings is in range [1, 10,000].
 */

public class PermutationInString567 {
 public boolean checkInclusion(String s1, String s2) {
 if (s1 == null || s2 == null || s1.length() > s2.length()) return false;
 int[] map = new int[26];
 int M = 0;
 for (char c: s1.toCharArray()) {
 if (map[c - 'a'] == 0) M++;
 map[c - 'a']++;
 }
 char[] chars2 = s2.toCharArray();
 int N2 = s2.length();
 int N1 = s1.length();
 int left = 0;
 int right = 0;
 while (right < N2) {
 char rc = chars2[right++];
 map[rc - 'a']--;
 if (map[rc - 'a'] == 0) M--;
 if (M == 0) return true;
 if (right - left == N1) {
 char lc = chars2[left++];
 if (map[lc - 'a'] == 0) M++;
 map[lc - 'a']++;
 }
 }
 return false;
 }

}