Anagram Permutation in String
A medium Strings problem included in Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Strings
- Sheets
- 1
- Core for
- 13 roles
- Platform
- LeetCode
The problem
Given two strings s1 and s2, check whether any permutation of s1 appears as a substring in s2.
Example 1
- Input
- s1="ab", s2="eidbaooo"
- Output
- true
Example 2
- Input
- s1="ab", s2="eidboaoo"
- Output
- false
Example 3
- Input
- s1="adc", s2="dcda"
- Output
- true
Constraints
- 1 <= s1.length, s2.length <= 10^4
- strings consist of lowercase English letters
How to think about it
Updated 2026-09-09A permutation of s1 is any substring of s2 with the exact same character counts. Because every candidate must match s1's length exactly, the search space is a fixed-size sliding window of length |s1| moving across s2. Maintaining character frequencies incrementally as characters enter and exit lets you check validity without re-scanning the window.
Approaches, worst first
Sort every window
time O(n * k log k) · space O(k)
Extract every substring of s2 with length equal to s1, sort it, and compare it to the sorted version of s1. Sorting each candidate window takes O(k log k) time and performs unnecessary reordering work on overlapping slices.
Fixed sliding window with match countWrite this one
time O(n) · space O(1)
Maintain frequency arrays for s1 and the current window in s2. Track how many of the 26 alphabet letters currently have identical counts. As the window slides one step, update the entering and leaving characters: if matches reaches 26, a valid permutation is present.
Where people lose marks · 3
- When s1 is strictly longer than s2, no permutation can exist; return false immediately without attempting to initialize a negative or out-of-bounds window.
- Comparing the entire 26-element array naively on every step yields O(26 * n) work; tracking a single matches integer that updates in O(1) per step keeps the inner loop tight.
- Forgetting to update the match count properly when an entering or exiting letter's count matches before the adjustment but mismatches after, or vice versa.
The theory behind it
Strings — the ground this problem stands on. All Strings problems
What Strings is
A string is an ordered necklace of text characters, like letters printed along a ribbon of paper. Each character sits at an exact numeric slot, holding a glyph such as a letter, punctuation mark, or digit. In many programming languages, ribbons cannot be edited after creation, meaning changing a single character requires pressing an entirely new ribbon from scratch.
When to reach for it
Reach for string techniques when inputs consist of words, DNA sequences, serialized data formats, or sentences. Clues include questions testing palindromes, anagram matches, substring patterns, parenthesis balancing, or character frequency counts. Whenever an algorithm asks to transform capitalization, parse structured tokens, or compute edits between two phrases, string representations are the core subject.
How the pattern works
Think of characters as small integer codes ranging across standard character sets. Frequency tables with fixed sizes often replace heavy hash maps when tallying occurrences. For search tasks, maintain rolling state using character indices or sliding borders. When building output text through repeated appends, accumulate pieces inside a mutable list or string builder rather than concatenating strings directly, avoiding quadratic copy overhead.
What each operation costs
| Operation | Time |
|---|---|
| read character by index | O(1) |
| concatenate two strings of total length n | O(n) |
| compare two strings of length n | O(n) |
What usually goes wrong with Strings
- Concatenating strings inside a loop using the plus operator, which silently creates full copies on each iteration and turns linear routines into quadratic slowdowns.
- Assuming all characters fall strictly within lowercase English letters without validating spaces, uppercase variants, punctuation marks, or multi-byte unicode symbols.
- Confusing substring length with end index when slicing, causing unexpected off-by-one truncations in languages that take length versus exclusive end position.
Which roles need this problem
Strings is a core topic for these 13 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 7 more roles, including Data Engineer, Data Analyst, Embedded / Firmware Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Strings problems
Problem set and role mapping as of .