Skip to main content

Contiguous Anagram Window Locator

medium
Hash TableArrayStringSliding WindowSliding Window
Asked atAmazonMicrosoftGoogleMeta

Problem Description

You are given two strings `text` and `pattern`. Return a list of all starting indices in `text` where a contiguous substring of length `pattern.length` is an anagram of `pattern`.

An anagram is a rearrangement of all characters of the original string.

Return the starting indices in any order.

**Example 1:**
```
Input: text = "cbaebabacd", pattern = "abc"
Output: [0, 6]
```
Explanation: Substring at index 0 is "cba" (anagram of "abc"); substring at index 6 is "bac" (anagram of "abc").

**Example 2:**
```
Input: text = "aababcd", pattern = "ab"
Output: [0, 1, 3]
```
Explanation: "ab", "ba", "ab" are all anagrams of "ab".

Constraints

  • 1 <= text.length <= 10^5
  • 1 <= pattern.length <= text.length
  • text and pattern consist of lowercase English letters only

Follow-up

Can you extend this to handle patterns over an arbitrary alphabet (not just lowercase letters) while keeping the same time complexity?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.