LeetCode 567: Permutation in String

Explanation

To solve this problem, we can use a sliding window approach. We can maintain a count of characters in s1 and a sliding window of the same length as s1 in s2. We iterate through s2, updating the character counts in the window. At each step, we check if the counts in the window match the counts of s1. If they do, we return true. If not, we slide the window by removing the leftmost character and adding the rightmost character. We continue this process until we reach the end of s2. If we don't find a match, we return false.

Algorithm:

1. Create two arrays countS1 and countWindow to store the counts of characters in s1 and the current window in s2.
2. Initialize the counts of characters in s1.
3. Iterate through s2, updating the count of characters in the window.
4. At each step, check if the counts in the window match the counts of s1.
5. If the counts match, return true.
6. If not, slide the window by removing the leftmost character and adding the rightmost character.
7. Continue this process until the end of s2. If no match is found, return false.

Time Complexity: O(n), where n is the length of s2. Space Complexity: O(1) since the count arrays have a fixed size of 26 for lowercase English letters.

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