Practice/Amazon/Leetcode 438. Find All Anagrams in a String

Leetcode 438. Find All Anagrams in a String

CodingMust

Problem

You are given two strings: text and pattern. Your task is to find all starting indices in text where a substring matches pattern as an anagram. Two strings are anagrams if they contain the same characters with the same frequencies, regardless of order.

Return a list of all starting positions (indices) in text where an anagram of pattern begins. The indices should be returned in ascending order.

Requirements

1. Identify all positions in text where a substring of length equal to pattern is an anagram of pattern
2. Return the starting indices as a list in ascending order
3. Both strings contain only lowercase English letters
4. If no anagrams are found, return an empty list

Constraints

• 1 ≤ length of text, pattern ≤ 30,000
• Both strings consist only of lowercase English letters ('a' to 'z')
• The solution should handle cases where pattern is longer than text
• Time complexity should be O(n) where n is the length of text
• Space complexity should be O(1) since we only use fixed-size arrays (26 letters)

Examples

Example 1:

` Input: text = "cbaebabacd", pattern = "abc" Output: [0, 6] Explanation:

• At index 0: "cba" is an anagram of "abc"
• At index 6: "bac" is an anagram of "abc" `

Example 2:

` Input: text = "abab", pattern = "ab" Output: [0, 1, 2] Explanation:

• At index 0: "ab" is an anagram of "ab"
• At index 1: "ba" is an anagram of "ab"
• At index 2: "ab" is an anagram of "ab" `

Example 3:

Input: text = "abcdef", pattern = "xyz" Output: [] Explanation: No substring of "abcdef" contains all the letters in "xyz"