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

}