Command Palette

Search for a command to run...

Hectal
Problem 7.5 · Sliding WindowMedium

Permutation in String

PatternSliding Window: Fixed SizeFrequency Counting

What it teaches: A fixed window the size of the pattern, compared by letter counts: anagram search in O(n).

Practise it on judges as “Permutation in String”.

The problem

Given strings s1 and s2, return true if s2 contains a permutation of s1 as a substring (some window of s2 is an anagram of s1).

Example 1

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

s2 contains "ba".

Example 2

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

Constraints

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

Pattern clues in the wording

  • → A permutation (anagram) of a fixed-length pattern inside a longer string
  • → Window length = pattern length

These clues point to Sliding Window: Fixed Size: Keep a window of exactly k elements; add the element entering and remove the one leaving instead of recomputing.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s1 = "ab"
s2 = "eidbaooo"
true
2
s1 = "ab"
s2 = "eidboaoo"
false

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: fixed window of counts · O(n) (plus 26 per step in the simple version)
1

Optimal: fixed window of counts

Time O(n) (plus 26 per step in the simple version) Space O(26)

Count s1. Slide a window of length m over s2 with its own counts; whenever the 26 counts match, return true. Track the number of matching letters to compare in O(1).

▶ Dry run: Window of length 2s1 = "ab", s2 = "eidbaooo"
e
0
i
1
d
2
b
3
a
4
o
5
o
6
o
7

Step 1/4Window "ei": counts don't match {a: 1, b: 1}.

Approach 1
import java.util.Arrays;

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

Verdict: Linear scan of s2.

Before you submit

Edge cases and common mistakes

Test these inputs

  • s1 longer than s2 → false
  • s1 equals s2
  • Repeated letters in s1

Mistakes people make

  • Comparing sorted substrings for every window: O(n · m log m).
  • Removing the leaving character at the wrong index.

Interview

Follow-up questions

How would you return all start indexes of anagrams of p in s?