LeetCode //C - 567. Permutation in String

567. Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.
 

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

Constraints:

• $1<=s1.length,s2.length<=10^4$
• s1 and s2 consist of lowercase English letters.

From: LeetCode
Link: 567. Permutation in String

Solution:

Ideas:

1. Precompute frequency counts:

• We create two frequency arrays count1 (for s1) and count2 (for s2’s first window of size len1).

2. Compare initial window:

• If count1 matches count2, return true.

3. Sliding window mechanism:

• Slide through s2 by removing the leftmost character and adding the next character in sequence.
• Update matches to track how many frequency counts match.

4. Efficiency:

• Time Complexity: O(n) (where n is the length of s2)
• Space Complexity: O(1) (only 26 fixed-size arrays)

Code:

bool checkInclusion(char* s1, char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    if (len1 > len2) return false;

    int count1[26] = {0}, count2[26] = {0};

    // Initialize frequency counts for s1 and the first window in s2
    for (int i = 0; i < len1; i++) {
        count1[s1[i] - 'a']++;
        count2[s2[i] - 'a']++;
    }

    // Check if the first window is a permutation
    int matches = 0;
    for (int i = 0; i < 26; i++) {
        if (count1[i] == count2[i]) matches++;
    }

    // Sliding window through s2
    for (int i = 0; i < len2 - len1; i++) {
        if (matches == 26) return true;

        // Remove the first character of the window
        int left = s2[i] - 'a';
        count2[left]--;
        if (count2[left] == count1[left]) {
            matches++;
        } else if (count2[left] + 1 == count1[left]) {
            matches--;
        }

        // Add the next character to the window
        int right = s2[i + len1] - 'a';
        count2[right]++;
        if (count2[right] == count1[right]) {
            matches++;
        } else if (count2[right] - 1 == count1[right]) {
            matches--;
        }
    }

    return matches == 26;
}