567. Permutation in String

Description

Given two strings s1 and s2, your goal is to determine if one string's permutation is a substring of the other. Specifically, check whether any permutation of s1 exists within s2. If so, return true, otherwise return false.

Intuition

The problem requires checking for a permutation of one string (s1) within the other (s2). A permutation involves rearranging characters, but since it’s only rearranging, the count of each character must match between the two strings. Thus, the task boils down to comparing character frequencies in sliding windows of s2 that match the length of s1.

Approach

1. Initial Setup: - Create two frequency arrays (or maps) to store character counts for s1 and the first window in s2 of length equal to s1.
2. Sliding Window Technique: - Use a sliding window over s2, moving from the start to the end, adjusting the character frequencies dynamically for each window. - Compare the character counts of the current window in s2 with the character counts of s1. If they match, return true.
3. Edge Case: - If s1 is longer than s2, directly return false because it is impossible for a longer string to be a permutation of a shorter one.

Complexity

• Time Complexity: O(n), where n is the length of s2. Both string s1 and s2 are iterated once. Checking for matching frequencies is constant time since there are only 26 possible characters (for lowercase English letters).
• Space Complexity: O(1), because the frequency array or map has a fixed size of 26 for lowercase characters, regardless of input size.

Code

C++

class Solution {
public:

    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size()) return false;

        vector cache1(26, 0), cache2(26, 0);

        for (int i = 0; i < s1.size(); ++i) {
            cache1[s1[i] - 'a']++;
            cache2[s2[i] - 'a']++;
        }

        auto checkCache = [&]() {
            return cache1 == cache2;
        };

        if (checkCache()) return true;

        for (int i = s1.size(); i < s2.size(); ++i) {
            
            cache2[s2[i - s1.size()] - 'a']--;
            cache2[s2[i] - 'a']++;
            if (checkCache()) return true;
        }

        return false;
    }
};

Python

class Solution:

    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            
            return False

        cache1 = [0] * 26
        cache2 = [0] * 26

        for i in range(len(s1)):

            cache1[ord(s1[i]) - ord('a')] += 1
            cache2[ord(s2[i]) - ord('a')] += 1

        if cache1 == cache2:
            return True

        for i in range(len(s1), len(s2)):

            cache2[ord(s2[i - len(s1)]) - ord('a')] -= 1
            cache2[ord(s2[i]) - ord('a')] += 1
            if cache1 == cache2:
                return True

        return False

Java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;

        int[] cache1 = new int[26], cache2 = new int[26];
        for (int i = 0; i < s1.length(); ++i) {
            cache1[s1.charAt(i) - 'a']++;
            cache2[s2.charAt(i) - 'a']++;
        }

        if (Arrays.equals(cache1, cache2)) return true;

        for (int i = s1.length(); i < s2.length(); ++i) {
            cache2[s2.charAt(i - s1.length()) - 'a']--;
            cache2[s2.charAt(i) - 'a']++;
            if (Arrays.equals(cache1, cache2)) return true;
        }

        return false;
    }
}

JavaScript

var checkInclusion = function (s1, s2) {
    if (s1.length > s2.length) return false;

    const cache1 = {};
    const cache2 = {};

    for (let i = 0; i < s1.length; i++) {
        s1[i] in cache1 ? cache1[s1[i]]++ : cache1[s1[i]] = 1;
        s2[i] in cache2 ? cache2[s2[i]]++ : cache2[s2[i]] = 1;
    }

    const checkCache = (cache1, cache2) => {
        
        if (Object.values(cache1).length !== Object.values(cache2).length) return false;
        for (const key in cache1) {
            if (cache1[key] !== cache2[key]) {
                return false;
            }
        }
        return true;
    }

    if (checkCache(cache1, cache2)) return true;

    for (let i = s1.length; i < s2.length; i++) {
        let charOut = s2[i - s1.length];
        cache2[charOut] === 1 ? delete cache2[charOut] : cache2[charOut]--;

        let charIn = s2[i];
        cache2[charIn] ? cache2[charIn]++ : cache2[charIn] = 1;

        if (checkCache(cache1, cache2)) return true;
    }

    return false;
};