Permutation in String

Problem Description

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.

Examples

Constraints

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

Fixed-Size Window Frequencies

A permutation of a string contains the exact same characters in the exact same frequencies. This means we are searching for a substring in s2 of length s1.length that has a matching character frequency count. We can solve this efficiently by maintaining a sliding window of fixed size s1.length over s2. Instead of recomputing frequencies at each step, we maintain a frequency array. As the window shifts, we add the new incoming character to our frequency tracker and discard the outgoing character. If the frequency counts match at any point, a permutation exists.

Solution 1: Sliding Window Frequency Array

Slide a window of size s1.length over s2 while updating character frequencies.

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

        int[] s1Counts = new int[26];
        int[] s2Counts = new int[26];

        // Initialize first window
        for (int i = 0; i < n1; i++) {
            s1Counts[s1.charAt(i) - 'a']++;
            s2Counts[s2.charAt(i) - 'a']++;
        }

        if (matches(s1Counts, s2Counts)) return true;

        // Slide window across s2
        for (int i = n1; i < n2; i++) {
            s2Counts[s2.charAt(i) - 'a']++; // add incoming character
            s2Counts[s2.charAt(i - n1) - 'a']--; // remove outgoing character
            if (matches(s1Counts, s2Counts)) return true;
        }

        return false;
    }

    private boolean matches(int[] c1, int[] c2) {
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }
}

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1, n2 = len(s1), len(s2)
        if n1 > n2:
            return False

        s1_counts = [0] * 26
        s2_counts = [0] * 26

        # Initialize counts for s1 and the first window of s2
        for i in range(n1):
            s1_counts[ord(s1[i]) - ord('a')] += 1
            s2_counts[ord(s2[i]) - ord('a')] += 1

        if s1_counts == s2_counts:
            return True

        # Slide the window
        for i in range(n1, n2):
            s2_counts[ord(s2[i]) - ord('a')] += 1
            s2_counts[ord(s2[i - n1]) - ord('a')] -= 1
            if s1_counts == s2_counts:
                return True

        return False

#include <string>
#include <vector>

class Solution {
private:
    bool matches(const std::vector<int>& c1, const std::vector<int>& c2) {
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }

public:
    bool checkInclusion(std::string s1, std::string s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;

        std::vector<int> s1Counts(26, 0);
        std::vector<int> s2Counts(26, 0);

        for (int i = 0; i < n1; i++) {
            s1Counts[s1[i] - 'a']++;
            s2Counts[s2[i] - 'a']++;
        }

        if (matches(s1Counts, s2Counts)) return true;

        for (int i = n1; i < n2; i++) {
            s2Counts[s2[i] - 'a']++;
            s2Counts[s2[i - n1] - 'a']--;
            if (matches(s1Counts, s2Counts)) return true;
        }

        return false;
    }
};

Complexity Analysis

• Time Complexity: O(n + m) where n is the length of s1 and m is the length of s2. We iterate through the strings once and perform constant-time arrays comparison (26 operations).
• Space Complexity: O(1) auxiliary space as our frequency tracking arrays are fixed at size 26.

Where It Breaks

If the alphabet is arbitrary Unicode characters instead of lowercase English letters, the array approach fails. A hash map must be used instead, raising the space complexity to match the alphabet size.

Common Mistakes

• Incorrect check range: Beginning the sliding iteration without checking the initial window, which misses matches at the very beginning of s2.
• String length mismatches: Forgetting to return false immediately if s1.length() > s2.length().

Frequently Asked Questions

Can we solve this by sorting? Yes. You can sort s1 and sort every substring of length s1.length() in s2. However, this takes O(m * n log n) time, which is highly inefficient.

Why is the frequency array size fixed at 26? The constraints specify that strings contain only lowercase English letters, which limits unique characters to 26.

← All Problems