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 <= 104
• s1 and s2 consist of lowercase English letters.

Approach 01:

class Solution {
public:
    bool checkInclusion(std::string pattern, std::string text) {
        std::vector<int> charFrequency(26);
        int remainingChars = pattern.length();

        for (const char ch : pattern)
            ++charFrequency[ch - 'a'];

        for (int left = 0, right = 0; right < text.length(); ++right) {
            if (--charFrequency[text[right] - 'a'] >= 0)
                --remainingChars;

            while (remainingChars == 0) {
                if (right - left + 1 == pattern.length())
                    return true;
                if (++charFrequency[text[left++] - 'a'] > 0)
                    ++remainingChars;
            }
        }

        return false;
    }
};

class Solution:
    def checkInclusion(self, pattern: str, text: str) -> bool:
        charFrequency = [0] * 26
        remainingChars = len(pattern)

        # Fill charFrequency with the frequency of characters in the pattern
        for ch in pattern:
            charFrequency[ord(ch) - ord('a')] += 1

        left = 0
        for right in range(len(text)):
            # Decrement the count for the current character
            if charFrequency[ord(text[right]) - ord('a')] > 0:
                remainingChars -= 1
            charFrequency[ord(text[right]) - ord('a')] -= 1

            # If all characters match, return True
            if remainingChars == 0:
                return True

            # Maintain the window size equal to the length of the pattern
            if right - left + 1 >= len(pattern):
                # Restore the count of the left character if it's part of the pattern
                if charFrequency[ord(text[left]) - ord('a')] >= 0:
                    remainingChars += 1
                charFrequency[ord(text[left]) - ord('a')] += 1
                left += 1

        return False

Time Complexity

• Building the frequency map:

  The function first initializes a frequency vector for the characters in the pattern string. This takes \(O(m)\), where \(m\) is the length of the pattern.

• Sliding window over the text string:

  The sliding window moves across the text string, examining each character. For each character, updating the frequency vector and checking the window size take constant time, \(O(1)\), and the window slides across the entire text string of length \(n\). Thus, the time complexity of this step is \(O(n)\), where \(n\) is the length of the text.

• Overall Time Complexity:

  The overall time complexity is \(O(n + m)\), where \(n\) is the length of the text and \(m\) is the length of the pattern. This accounts for both the setup of the frequency map and the sliding window process.

Space Complexity

• Auxiliary Space:

  The algorithm uses a frequency vector of size 26 (for the lowercase alphabet), which requires constant space, \(O(1)\). No additional data structures that scale with the input size are used.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the algorithm only uses a fixed amount of extra space, independent of the input size.