Permutation in String

Medium Problem 24 of 151 Java and Python

Problem

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

In other words: is there a substring of s2 that uses exactly the letters of s1?

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Why: "ba" is a permutation of "ab".

Example 2

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

Constraints

1 ≤ s1.length, s2.length ≤ 10⁴
Both strings contain only lowercase English letters.

Explanation

Any match has exactly s1.length characters, so slide a window of that fixed size over s2 and compare letter counts.

Moving the window changes only two counts (one letter in, one out), so updating it is O(1).

Approach 1 · Naive

Sort every window

Time O(n · m log m)
Space O(m)

Sort s1. For every window of the same length in s2, sort it and compare.

Let m = s1.length and target = sorted s1.
For each start i, sort s2[i, i + m) and compare with target.

Java

import java.util.*;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length();
        char[] target = s1.toCharArray();
        Arrays.sort(target);
        for (int i = 0; i + m <= s2.length(); i++) {
            char[] window = s2.substring(i, i + m).toCharArray();
            Arrays.sort(window);
            if (Arrays.equals(window, target)) {
                return true;
            }
        }
        return false;
    }
}

Python

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m = len(s1)
        target = sorted(s1)
        for i in range(len(s2) - m + 1):
            if sorted(s2[i:i + m]) == target:
                return True
        return False

Approach 2 · Optimal

Fixed window of letter counts

Time O(26 · n) = O(n)
Space O(1)

Count the letters of s1. Keep counts for the current window of s2, adding the entering letter and removing the leaving one, and compare the two count arrays.

If s1 is longer than s2, return false.
Count s1 and the first m letters of s2.
If the counts match, return true. Slide: add s2[i], remove s2[i - m], compare again.

Java

import java.util.*;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length();
        if (m > s2.length()) {
            return false;
        }
        int[] need = new int[26];
        int[] window = new int[26];
        for (int i = 0; i < m; i++) {
            need[s1.charAt(i) - 'a']++;
            window[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(need, window)) {
            return true;
        }
        for (int i = m; i < s2.length(); i++) {
            window[s2.charAt(i) - 'a']++;
            window[s2.charAt(i - m) - 'a']--;
            if (Arrays.equals(need, window)) {
                return true;
            }
        }
        return false;
    }
}

Python

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m = len(s1)
        if m > len(s2):
            return False
        need, window = [0] * 26, [0] * 26
        for i in range(m):
            need[ord(s1[i]) - ord('a')] += 1
            window[ord(s2[i]) - ord('a')] += 1
        if need == window:
            return True
        for i in range(m, len(s2)):
            window[ord(s2[i]) - ord('a')] += 1
            window[ord(s2[i - m]) - ord('a')] -= 1
            if need == window:
                return True
        return False

Complexity compared

Approach	Time	Space
Naive Sort every window	O(n · m log m)	O(m)
Optimal Fixed window of letter counts	O(26 · n) = O(n)	O(1)

Key takeaways

"Some rearrangement of X inside Y" = fixed-size window + counts.
Same idea solves Find All Anagrams in a String: collect every start where the counts match.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem