Check If a String Contains a Permutation of Another

Medium20–25 min

Topics

StringSliding WindowHash Table

Companies

AmazonMicrosoftGoogleFacebook

Given two lowercase strings s1 and s2, return true if s2 contains a contiguous substring that is a permutation (an anagram, rearranged) of s1. A permutation doesn't care about order — only about having exactly the same letters, with exactly the same counts. That turns this from a string-matching problem into a counting problem: a window of s2 is a match precisely when its 26-letter frequency count equals s1's. Rebuilding that count for every window works, but the sliding window technique keeps the count updated in O(1) per slide — bump the letter entering, drop the letter leaving — instead of recounting all of s1.length letters every time.

Test Case 1:

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

Output:true

Explanation:The substring "ba" at index 3-4 of s2 is a permutation of s1.

Test Case 2:

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

Output:false

Explanation:No window of length 2 in s2 has exactly one 'a' and one 'b'.

Test Case 3:

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

Output:true

Explanation:The substring "cda" at index 1-3 of s2 is a permutation of s1.

Constraints

◆1 ≤ s1.length ≤ s2.length ≤ 10⁴
◆s1 and s2 consist of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s1 (lowercase) — 2-6 lowercase letterss2 (lowercase) — 4-14 lowercase letters, at least as long as s1

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

↑left

↑right

Variables

window"ei"

INITIALIZE

Build the letter-count of s1's frequency array and the very first window of s2, "ei".

Step 1 / 8

Approach & Solutions

Brute Force

Brute

Build a 26-letter frequency count for s1. Then for every window of length s1.length in s2, build that window's own frequency count from scratch and compare it against s1's. Correct, but rebuilding a fresh count for every single window throws away almost all of the work done for the window right before it.

TimeO(n · 26)

SpaceO(1)

Java

Try it out

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

Optimal — Sliding Window

Optimal

Build s1's 26-letter frequency count once, and the very first window's frequency count once. Compare them. Then slide the window one character at a time: bump the count of the character entering on the right, drop the count of the character leaving on the left, and compare again — no need to rebuild the whole window's count from scratch on every slide.

TimeO(n)