Permutation in String

Permutation in String

What is this problem about?

The Permutation in String problem asks whether any permutation of string s1 appears as a contiguous substring of string s2. This is equivalent to checking if any window of length len(s1) in s2 has the same character frequencies as s1. This Permutation in String coding problem is a classic fixed-size sliding window with character counting. The hash table, two pointers, sliding window, and string interview pattern is the core.

Why is this asked in interviews?

Apple, Cisco, Goldman Sachs, Microsoft, Meta, Amazon, TikTok, Google, Bloomberg, and Adobe ask this because it's the canonical anagram-in-string problem. It tests the fixed-size sliding window with two character frequency arrays (or a single difference counter). This is a foundational sliding window problem.

Algorithmic pattern used

Fixed-size sliding window with frequency count. Build frequency arrays for s1 and the first len(s1) characters of s2. Maintain a matches counter (count of characters where frequencies are equal). Slide the window: add the new right character, remove the left character, update matches. When matches == 26, a valid window is found.

Example explanation

s1="ab", s2="eidbaooo". Window size=2.

• Window "ei": freq[e]=1,freq[i]=1. No match with {a:1,b:1}.
• Window "id": still no match.
• Window "db": no match.
• Window "ba": freq[b]=1,freq[a]=1. Matches {a:1,b:1} ✓. Return true.

Common mistakes candidates make

• Using sorting for each window (O(n * k log k) instead of O(n)).
• Recomputing frequency counts from scratch per window.
• Using a dictionary comparison per window (O(26) = O(1) per step, which is acceptable, but the matches counter approach is faster in practice).
• Off-by-one in window initialization.

Interview preparation tip

Permutation in String is the template for all "fixed-window anagram detection" problems. Master the matches counter optimization: track the count of positions where s1_freq[c] == window_freq[c]. When matches==26, found a valid window. This O(n) approach is the cleanest. Practice applying it to: "find all anagrams in string," "minimum window containing all characters." The sliding window + frequency array pattern is universally applicable.