Permutation in String

LeetCode Q 567 - Permutation in String

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].

Solution : Sliding Window

1. Swap String s1, count the times each char appears.
2. Get the first s1.length() char of String s2, to check if the times of each char in s2 mataches that in s1.
   • If it matches, we return true.
   • If not, we apply slinding window algorithm to keep checking, increasing the last char and decreasing the first char.

Code:

public boolean checkInclusion(String s1, String s2) {
	
	if (s1.length() > s2.length()) return false;
	
	int[] count = new int[26];
	
	for (int i = 0; i < s1.length(); i++) {
		count[s1.charAt(i) - 'a']++;
		count[s2.charAt(i) - 'a']--;
	}
	
	if (allZeros(count)) return true;
	
	for (int i = s1.length(); i < s2.length(); i++) {
		count[s2.charAt(i) - 'a']--;
		count[s2.charAt(i - s1.length()) - 'a']++;
		if (allZeros(count)) return true;
	}
	
	return false;    
}

private boolean allZeros(int[] count) {
    for (int c: count)	
    	if (c != 0) return false;

    return true;
}