Permutation in String

Description

You are given two strings s1 and s2, both consisting of lowercase English letters.

Return true if s2 contains any permutation of s1 as a contiguous substring, or false otherwise.

A permutation of a string is any rearrangement of its characters. For example, "abc" has permutations "abc", "acb", "bac", "bca", "cab", and "cba". You do not need to generate these permutations — you only need to determine whether any one of them appears somewhere inside s2.

Put differently: does s2 contain a substring of the same length as s1 that uses exactly the same characters with exactly the same frequencies?

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

Explanation: The substring "ba" starting at index 3 in s2 is a permutation of "ab". Both contain exactly one 'a' and one 'b', just in different order. Since a permutation of s1 exists as a contiguous substring inside s2, we return true.

Example 2

Input: s1 = "ab", s2 = "eidboaoo"

Output: false

Explanation: Although s2 contains both 'a' and 'b', they never appear next to each other as a contiguous substring of length 2. The character 'b' is at index 3, and 'a' is at index 5 — separated by 'o'. No substring of length 2 in s2 has the same character frequencies as "ab", so we return false.

Example 3

Input: s1 = "adc", s2 = "dcda"

Output: true

Explanation: The substring "dcd" (indices 0-2) has characters d, c, d — that does not match "adc" (a:1, d:1, c:1). But the substring "cda" (indices 1-3) has c:1, d:1, a:1, which exactly matches the frequency of "adc". So we return true.

Constraints

1 ≤ s1.length, s2.length ≤ 10^4
s1 and s2 consist of lowercase English letters only

Editorial

Brute Force

Intuition

The most direct approach: if a permutation of s1 exists as a substring of s2, then somewhere in s2 there is a contiguous block of characters that, when rearranged, spells s1. Two strings are permutations of each other if and only if they contain the same characters in the same quantities — which means sorting both would produce the same result.

So we can sort s1 once, then check every substring of s2 that has the same length as s1. For each such substring, we sort it and compare with the sorted s1. If they match, we have found a permutation.

Think of it like having a bag of Scrabble tiles. You have a target word (s1), and you are scanning along a shelf of tiles (s2). At each position you grab a handful of tiles equal in number to the target word, sort them alphabetically, and check if they spell the same sorted sequence as your target. If they do, those tiles can rearrange into the target.

Step-by-Step Explanation

Let's trace through with s1 = "ab", s2 = "eidbaooo":

Step 1: Sort s1 → "ab". The window size m = len(s1) = 2. We will check every substring of s2 that has length 2.

Step 2: Window at indices [0, 1] → substring "ei". Sort it → "ei". Compare "ei" with "ab" → not equal. Move on.

Step 3: Window at indices [1, 2] → substring "id". Sort it → "di". Compare "di" with "ab" → not equal. Move on.

Step 4: Window at indices [2, 3] → substring "db". Sort it → "bd". Compare "bd" with "ab" → not equal. Move on.

Step 5: Window at indices [3, 4] → substring "ba". Sort it → "ab". Compare "ab" with "ab" → MATCH! The substring "ba" is a permutation of "ab".

Step 6: Return true. We found a match on the 4th window. In the worst case, we would check all (n - m + 1) = 7 windows.

Algorithm

Sort s1 to get sorted_s1
Let m = len(s1), n = len(s2)
If m > n, return false immediately (s1 cannot fit inside s2)
For each starting index i from 0 to n - m:
- Extract substring s2[i : i + m]
- Sort this substring
- If sorted substring equals sorted_s1, return true
If no match found after all windows, return false

Code

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if (m > n) return false;

        string sorted_s1 = s1;
        sort(sorted_s1.begin(), sorted_s1.end());

        for (int i = 0; i <= n - m; i++) {
            string window = s2.substr(i, m);
            sort(window.begin(), window.end());
            if (window == sorted_s1) return true;
        }
        return false;
    }
};

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

        sorted_s1 = sorted(s1)

        for i in range(n - m + 1):
            window = sorted(s2[i:i + m])
            if window == sorted_s1:
                return True
        return False

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

        char[] sortedS1 = s1.toCharArray();
        Arrays.sort(sortedS1);

        for (int i = 0; i <= n - m; i++) {
            char[] window = s2.substring(i, i + m).toCharArray();
            Arrays.sort(window);
            if (Arrays.equals(window, sortedS1)) return true;
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O((n - m + 1) × m log m)

We iterate through (n - m + 1) possible window positions. For each position, we extract a substring of length m and sort it, which takes O(m log m). The comparison itself is O(m). So total time is O((n - m + 1) × m log m). With n and m both up to 10^4, in the worst case this could be around 10^4 × 14 × 10^4 ≈ 10^9, which is far too slow.

Space Complexity: O(m)

We create a sorted copy of each window substring, requiring O(m) space.

Why This Approach Is Not Efficient

The brute force sorts every window from scratch, even though adjacent windows overlap by m - 1 characters. When we slide from window "ei" to window "id", we drop one character and add one — but we re-sort all m characters as if the window were entirely new.

Sorting costs O(m log m) per window, and with up to 10^4 windows each of size up to 10^4, the total work approaches 10^9 operations — well beyond typical time limits.

Key insight: We do not actually need sorted order. Two strings are permutations of each other if and only if they have identical character frequency counts. Counting character frequencies takes O(m) per window (instead of O(m log m) for sorting), and since we only have 26 lowercase letters, comparing two frequency arrays takes O(26) = O(1). This eliminates the expensive sorting step entirely.

Better Approach - Frequency Array Matching

Intuition

Instead of sorting, we count how many times each character appears. If the character counts for a window of s2 match the character counts for s1, the window is a permutation of s1.

We precompute the frequency array for s1 (26 slots, one per letter). Then for each window of length m in s2, we build a fresh frequency array from the window's characters and compare the two arrays.

Imagine counting coins instead of sorting them. If you have a pile of coins (the window) and a reference pile (s1), you don't need to arrange them in order — just count how many pennies, nickels, dimes, and quarters are in each pile. If the counts match, the piles are identical in composition.

Step-by-Step Explanation

Let's trace with s1 = "ab", s2 = "eidbaooo":

Step 1: Build s1's frequency array: s1Count['a'] = 1, s1Count['b'] = 1. All other entries are 0. Window size m = 2.

Step 2: Window [0, 1] = "ei". Build frequency: winCount['e'] = 1, winCount['i'] = 1. Compare with s1Count: 'a' mismatch (1 vs 0), 'b' mismatch (1 vs 0), 'e' mismatch (0 vs 1), 'i' mismatch (0 vs 1). Not a match.

Step 3: Window [1, 2] = "id". Build frequency from scratch: winCount['i'] = 1, winCount['d'] = 1. Compare: still 4 mismatches. Not a match.

Step 4: Window [2, 3] = "db". Build frequency: winCount['d'] = 1, winCount['b'] = 1. Compare: 'a' mismatch (1 vs 0), 'b' matches (1 == 1), 'd' mismatch (0 vs 1). Not a full match.

Step 5: Window [3, 4] = "ba". Build frequency: winCount['b'] = 1, winCount['a'] = 1. Compare with s1Count: 'a' matches (1 == 1), 'b' matches (1 == 1), all others are 0 == 0. Full match!

Step 6: Return true. The substring "ba" has the same character frequencies as "ab".

Notice we rebuilt the frequency array from scratch for each window. For a window of size m, this rebuilding costs O(m). Since we check (n - m + 1) windows, the total work is O((n - m + 1) × m).

Algorithm

Build a frequency array s1Count of size 26 from s1
Let m = len(s1), n = len(s2). If m > n, return false.
For each starting index i from 0 to n - m:
- Build a frequency array winCount of size 26 from s2[i : i + m]
- Compare winCount with s1Count element by element
- If all 26 entries match, return true
Return false

Code

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if (m > n) return false;

        vector<int> s1Count(26, 0);
        for (char c : s1) s1Count[c - 'a']++;

        for (int i = 0; i <= n - m; i++) {
            vector<int> winCount(26, 0);
            for (int j = i; j < i + m; j++) {
                winCount[s2[j] - 'a']++;
            }
            if (winCount == s1Count) return true;
        }
        return false;
    }
};

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

        s1_count = [0] * 26
        for c in s1:
            s1_count[ord(c) - ord('a')] += 1

        for i in range(n - m + 1):
            win_count = [0] * 26
            for j in range(i, i + m):
                win_count[ord(s2[j]) - ord('a')] += 1
            if win_count == s1_count:
                return True
        return False

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

        int[] s1Count = new int[26];
        for (char c : s1.toCharArray()) s1Count[c - 'a']++;

        for (int i = 0; i <= n - m; i++) {
            int[] winCount = new int[26];
            for (int j = i; j < i + m; j++) {
                winCount[s2.charAt(j) - 'a']++;
            }
            if (Arrays.equals(winCount, s1Count)) return true;
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O((n - m + 1) × m)

For each of the (n - m + 1) window positions, we scan all m characters to build the frequency array, then compare 26 entries in O(1). The dominant cost is the frequency building: O((n - m + 1) × m). With n = m = 10^4, this is about 10^8 — borderline for typical time limits.

Space Complexity: O(1)

We use two frequency arrays of fixed size 26, independent of input size. This is O(1) auxiliary space.

Why This Approach Is Not Efficient

The Better approach eliminates sorting but still rebuilds the frequency array from scratch for each window. When we move from window "ei" to window "id", we discard the entire frequency count and recount all m characters — even though m - 1 of them are the same!

Specifically, windows "ei" and "id" share the character 'i'. The only change is removing 'e' from the left and adding 'd' on the right. If we could just update the existing frequency count instead of rebuilding it, each slide would cost O(1) instead of O(m).

This is the sliding window insight: maintain the window's frequency array incrementally. When the window slides one position to the right, decrement the count of the character leaving on the left, and increment the count of the character entering on the right. This reduces the per-window cost from O(m) to O(1), giving an overall O(n) algorithm.

Optimal Approach - Sliding Window with Match Counter

Intuition

We maintain a fixed-size window of length m (= len(s1)) that slides across s2 one character at a time. Instead of rebuilding the frequency array each time, we update it incrementally:

When a character enters the window on the right, increment its count in s2Count
When a character leaves the window on the left, decrement its count in s2Count

To check whether the window is a permutation, we could compare all 26 entries of s1Count and s2Count at each step — but even that O(26) comparison can be optimized. We maintain a matches variable that counts how many of the 26 letter positions currently have s1Count[c] == s2Count[c]. When matches reaches 26, every letter has the same frequency in both strings, meaning the window is a valid permutation.

The clever part: each time we modify s2Count[c] (either incrementing or decrementing), we check whether that specific position c transitioned from matching to non-matching (decrement matches) or from non-matching to matching (increment matches). This keeps the matches variable updated in O(1) per character change.

Imagine a dashboard with 26 green/red lights, one per letter. A light is green when s1 and the window have the same count for that letter, red otherwise. Each time the window slides, at most two lights change (one for the added character, one for the removed character). When all 26 lights are green simultaneously, you have found a permutation.

Step-by-Step Explanation

Let's trace through with s1 = "ab", s2 = "eidbaooo":

Step 1: Build s1Count: a=1, b=1, all others 0. Window size m = 2.

Step 2: Initialize s2Count from first m characters "ei": e=1, i=1. Count initial matches across all 26 positions: positions a, b, e, i each have a mismatch (s1 vs s2 differ). The other 22 positions all have count 0 == 0. So matches = 22.

Step 3: Check: matches = 22 ≠ 26. Not a permutation yet. Begin sliding.

Step 4: Slide right — add s2[2] = 'd' to window. s2Count['d'] goes from 0 to 1. Before: s1Count['d']=0 == s2Count['d']=0 (was a match). After: s1Count['d']=0 ≠ s2Count['d']=1 (now a mismatch). Lost a match → matches = 21.

Step 5: Slide left — remove s2[0] = 'e' from window. s2Count['e'] goes from 1 to 0. Before: s1Count['e']=0 ≠ s2Count['e']=1 (was a mismatch). After: s1Count['e']=0 == s2Count['e']=0 (now a match). Gained a match → matches = 22. Window is now [1, 2] = "id".

Step 6: Check: matches = 22 ≠ 26. Still 4 mismatches (a, b, i, d). Continue sliding.

Step 7: Slide right — add s2[3] = 'b'. s2Count['b'] goes from 0 to 1. Before: s1Count['b']=1 ≠ s2Count['b']=0 (mismatch). After: s1Count['b']=1 == s2Count['b']=1 (match!). Gained a match → matches = 23.

Step 8: Slide left — remove s2[1] = 'i'. s2Count['i'] goes from 1 to 0. Before: s1Count['i']=0 ≠ s2Count['i']=1 (mismatch). After: s1Count['i']=0 == s2Count['i']=0 (match!). Gained a match → matches = 24. Window is now [2, 3] = "db".

Step 9: Check: matches = 24 ≠ 26. Two mismatches remain: position 'a' (need 1, have 0) and position 'd' (need 0, have 1). We have 'b' but also 'd', and we are missing 'a'. Continue.

Step 10: Slide right — add s2[4] = 'a'. s2Count['a'] goes from 0 to 1. Before: s1Count['a']=1 ≠ s2Count['a']=0 (mismatch). After: s1Count['a']=1 == s2Count['a']=1 (match!). Gained a match → matches = 25.

Step 11: Slide left — remove s2[2] = 'd'. s2Count['d'] goes from 1 to 0. Before: s1Count['d']=0 ≠ s2Count['d']=1 (mismatch). After: s1Count['d']=0 == s2Count['d']=0 (match!). Gained a match → matches = 26!

Step 12: Check: matches = 26! All 26 letter frequencies match between s1 and the current window "ba" (indices [3, 4]). This means "ba" is a permutation of "ab". Return true.

Sliding Window with Match Counter — Finding Permutation of "ab" in "eidbaooo" — Watch how the fixed-size window slides across s2, incrementally updating character frequencies and the matches counter. When matches reaches 26, all character frequencies align — a permutation is found.

Algorithm

If len(s1) > len(s2), return false
Build frequency array s1Count[26] from s1
Build frequency array s2Count[26] from the first m characters of s2
Count initial matches = number of positions i (0 to 25) where s1Count[i] == s2Count[i]
Slide the window from left pointer l=0, right pointer r=m to r < n:
a. If matches == 26, return true
b. Add right character s2[r] to window:
- Increment s2Count[s2[r]]
- If s2Count now equals s1Count at that position → matches++
- Else if s2Count just exceeded s1Count (was equal, now one more) → matches--
  c. Remove left character s2[l] from window:
- Decrement s2Count[s2[l]]
- If s2Count now equals s1Count at that position → matches++
- Else if s2Count just went below s1Count (was equal, now one less) → matches--
  d. Increment l
Return matches == 26 (check the last window)

Code

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if (m > n) return false;

        vector<int> s1Count(26, 0), s2Count(26, 0);
        for (int i = 0; i < m; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }

        int matches = 0;
        for (int i = 0; i < 26; i++) {
            if (s1Count[i] == s2Count[i]) matches++;
        }

        int l = 0;
        for (int r = m; r < n; r++) {
            if (matches == 26) return true;

            // Add right character
            int idx = s2[r] - 'a';
            s2Count[idx]++;
            if (s2Count[idx] == s1Count[idx]) matches++;
            else if (s2Count[idx] == s1Count[idx] + 1) matches--;

            // Remove left character
            idx = s2[l] - 'a';
            s2Count[idx]--;
            if (s2Count[idx] == s1Count[idx]) matches++;
            else if (s2Count[idx] == s1Count[idx] - 1) matches--;
            l++;
        }
        return matches == 26;
    }
};

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

        s1_count = [0] * 26
        s2_count = [0] * 26
        for i in range(m):
            s1_count[ord(s1[i]) - ord('a')] += 1
            s2_count[ord(s2[i]) - ord('a')] += 1

        matches = sum(1 for i in range(26) if s1_count[i] == s2_count[i])

        l = 0
        for r in range(m, n):
            if matches == 26:
                return True

            # Add right character
            idx = ord(s2[r]) - ord('a')
            s2_count[idx] += 1
            if s2_count[idx] == s1_count[idx]:
                matches += 1
            elif s2_count[idx] == s1_count[idx] + 1:
                matches -= 1

            # Remove left character
            idx = ord(s2[l]) - ord('a')
            s2_count[idx] -= 1
            if s2_count[idx] == s1_count[idx]:
                matches += 1
            elif s2_count[idx] == s1_count[idx] - 1:
                matches -= 1
            l += 1

        return matches == 26

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

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        for (int i = 0; i < m; i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }

        int matches = 0;
        for (int i = 0; i < 26; i++) {
            if (s1Count[i] == s2Count[i]) matches++;
        }

        int l = 0;
        for (int r = m; r < n; r++) {
            if (matches == 26) return true;

            // Add right character
            int idx = s2.charAt(r) - 'a';
            s2Count[idx]++;
            if (s2Count[idx] == s1Count[idx]) matches++;
            else if (s2Count[idx] == s1Count[idx] + 1) matches--;

            // Remove left character
            idx = s2.charAt(l) - 'a';
            s2Count[idx]--;
            if (s2Count[idx] == s1Count[idx]) matches++;
            else if (s2Count[idx] == s1Count[idx] - 1) matches--;
            l++;
        }
        return matches == 26;
    }
}

Complexity Analysis

Time Complexity: O(n + m)

Building the initial frequency arrays and counting matches takes O(m + 26) = O(m). The sliding window loop runs (n - m) iterations, each doing O(1) work (two frequency updates, at most four comparison checks, one matches adjustment per update). Total: O(m + n) which simplifies to O(n) since m ≤ n.

Space Complexity: O(1)

We use two frequency arrays of fixed size 26 and a handful of integer variables. The space does not grow with input size. This is truly constant auxiliary space.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Permutation in String

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Frequency Array Matching

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Sliding Window with Match Counter

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis