#567 Permutation in String

Mediumsolve on LeetCode ↗

frequently reported atWalmart Microsoft Amazon Bloomberg Google Adobe

the problem

In plain words

Return true if some permutation of s1 appears as a substring of s2 — that is, if s2 contains an anagram of s1.

in s1 = "ab", s2 = "eidbaooo"

out true

"ba" is in s2.

in s1 = "ab", s2 = "eidboaoo"

out false

1 ≤ s1.length, s2.length ≤ 10⁴
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternSliding window (fixed size)Frequency counting

A permutation has the same letter counts. Slide a window of size |s1| over s2 and compare counts — the window changes by one letter in, one letter out.

solutions

From brute force to optimal

Two strings are permutations iff their sorted forms are equal.

Sort s1.
For each window of size m in s2, sort it and compare.

timeO((n − m + 1) · m log m)

n − m + 1 windows, each sorted in m log m (m = |s1|, n = |s2|).

spaceO(m)

A copy of each window.

javajava.util.*

1class Solution {2    public boolean checkInclusion(String s1, String s2) {3        char[] target = s1.toCharArray();4        Arrays.sort(target);5        for (int start = 0; start + s1.length() <= s2.length(); start++) {6            char[] window = s2.substring(start, start + s1.length()).toCharArray();7            Arrays.sort(window);                      // m log m per window8            if (Arrays.equals(window, target)) return true;9        }10        return false;11    }12}

Keep have[26] for the window; after each slide compare with need[26].

need = counts of s1.
Slide over s2: add the new letter, remove the letter m positions back.
If Arrays.equals(need, have) → true.

timeO(m + 26·n) = O(n)

Each slide is O(1) plus a 26-element comparison.

spaceO(1)

Two arrays of 26.

javajava.util.*

1class Solution {2    public boolean checkInclusion(String s1, String s2) {3        if (s1.length() > s2.length()) return false;4        int[] need = new int[26], have = new int[26];5        for (char c : s1.toCharArray()) need[c - 'a']++;6        int m = s1.length();7        for (int right = 0; right < s2.length(); right++) {8            have[s2.charAt(right) - 'a']++;9            if (right >= m) have[s2.charAt(right - m) - 'a']--;10            if (Arrays.equals(need, have)) return true;   // 26 comparisons11        }12        return false;13    }14}

Track how many letters are "off". Only the two letters that change can flip that number.

diff[c] = need − have; bad = letters with diff ≠ 0.
On each update, check whether diff[c] crossed 0 and adjust bad.
If the window is full and bad == 0 → true.

timeO(m + n)

Truly O(1) per slide — no 26-element comparison.

spaceO(1)

One array of 26 and a counter.

javajava.util.*

1class Solution {2    public boolean checkInclusion(String s1, String s2) {3        int m = s1.length();4        if (m > s2.length()) return false;5        int[] diff = new int[26];              // need minus have, per letter6        for (char c : s1.toCharArray()) diff[c - 'a']++;7        int bad = 0;                            // letters whose count is still off8        for (int d : diff) if (d != 0) bad++;9        for (int right = 0; right < s2.length(); right++) {10            int in = s2.charAt(right) - 'a';11            if (diff[in] == 0) bad++;           // was balanced, now off by one12            if (--diff[in] == 0) bad--;13            if (right >= m) {14                int out = s2.charAt(right - m) - 'a';15                if (diff[out] == 0) bad++;16                if (++diff[out] == 0) bad--;17            }18            if (right >= m - 1 && bad == 0) return true;19        }20        return false;21    }22}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public boolean checkInclusion(String s1, String s2) {3        int m = s1.length();4        if (m > s2.length()) return false;5        int[] diff = new int[26];              // need minus have, per letter6        for (char c : s1.toCharArray()) diff[c - 'a']++;7        int bad = 0;                            // letters whose count is still off8        for (int d : diff) if (d != 0) bad++;9        for (int right = 0; right < s2.length(); right++) {10            int in = s2.charAt(right) - 'a';11            if (diff[in] == 0) bad++;           // was balanced, now off by one12            if (--diff[in] == 0) bad--;13            if (right >= m) {14                int out = s2.charAt(right - m) - 'a';15                if (diff[out] == 0) bad++;16                if (++diff[out] == 0) bad--;17            }18            if (right >= m - 1 && bad == 0) return true;19        }20        return false;21    }22}

in the room

How to say it in the interview

talk track

Translate the problem: "permutation of s1 as a substring" = "a window of size |s1| with the same counts".
Give the Arrays.equals version first — it is already O(n). Offer the counter as an optimisation.

traps

Forgetting the early return when s1 is longer than s2.
Using a variable window — the size is fixed at |s1|.

what they ask next

Follow-ups

Find All Anagrams in a String (LC 438)?

The same window, but record every start where bad == 0 and keep sliding instead of returning — it's the next problem in this chapter.

before you submit

Edge cases to test

s1 longer than s2 → false straight away.
Repeated letters: "aab" needs two a's, not just "some a".
The match can be the very last |s1| letters of s2.
s1 equal to s2 → true.

practise next