mediumSliding Window

Permutation in String

Determine whether the second string contains a contiguous permutation of the first.

LeetCode ↗

Work through the cases

3 examples

Input notation

Two lowercase strings on separate lines, the pattern first.

Expected result

true or false.

Case 1

Input

ab
zzbaxy

Expected output

true

Case 2

Input

ab
zzacxy

Expected output

false

Case 3

Input

abc
ab

Expected output

false

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

A permutation of s1 is a window of length |s1| with the same counts. Sorting every window is wasteful. A sliding window stores the remaining counts versus s1 and need is how many letters are still off. Add the right end, drop the left, and succeed when need=0. Fixed length, one scan.

We use an array cnt to record the characters and their counts that need to be matched, and a variable need to record the number of different characters that still need to be matched. Initially, cnt contains the character counts from the string s1, and need is the number of different characters in s1.

Then we traverse the string s2. For each character, we decrement its corresponding value in cnt. If the decremented value equals 0, it means the current character's count in s1 is satisfied, and we decrement need. If the current index i is greater than or equal to the length of s1, we need to increment the corresponding value in cnt for s2[i-s1]. If the incremented value equals 1, it means the current character's count in s1 is no longer satisfied, and we increment need. During the traversal, if the value of need equals 0, it means all character counts are satisfied, and we have found a valid substring, so we return true.

Otherwise, if the traversal ends without finding a valid substring, we return false.

The time complexity is O(m + n), where m and n are the lengths of strings s1 and s2, respectively. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, the character set is lowercase letters, so the space complexity is constant.

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int need = 0;
        int[] cnt = new int[26];
        for (char c : s1.toCharArray()) {
            if (++cnt[c - 'a'] == 1) {
                ++need;
            }
        }
        int m = s1.length(), n = s2.length();
        for (int i = 0; i < n; ++i) {
            int c = s2.charAt(i) - 'a';
            if (--cnt[c] == 0) {
                --need;
            }
            if (i >= m) {
                c = s2.charAt(i - m) - 'a';
                if (++cnt[c] == 1) {
                    ++need;
                }
            }
            if (need == 0) {
                return true;
            }
        }
        return false;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.