Find All Anagrams in a String - Video Solutions

Problem Overview: Given a string s and a pattern p, return all starting indices in s where the substring is an anagram of p. Two strings are anagrams if they contain the same characters with the same frequency, just in a different order.

Approach 1: Sliding Window with Character Count (O(n) time, O(1) space)

This approach uses a fixed-size sliding window equal to the length of p. Maintain two frequency counters: one for the pattern and one for the current window in s. As the window moves one character at a time, increment the count for the incoming character and decrement the count for the outgoing character. When both frequency arrays match, the window represents an anagram and its starting index is recorded.

The key insight is that the window size never changes. Each step performs constant-time updates on a small character frequency array (typically size 26 for lowercase letters). This makes the entire scan linear. This technique is a classic application of the sliding window pattern combined with frequency counting.

Because the alphabet size is fixed, the extra memory remains constant, giving O(1) space complexity. This method is efficient and commonly expected in interviews for substring-anagram problems.

Approach 2: HashMap with Two-Pointer Technique (O(n) time, O(k) space)

This version uses a hash table to track character frequencies of the pattern and applies a dynamic window using two pointers (left and right). Expand the right pointer while updating counts in the map. When a character exceeds the required frequency, move the left pointer forward to restore a valid window.

Whenever the window length equals the pattern length and the frequency constraints are satisfied, the current left index is an anagram start. The two-pointer structure ensures each character is processed at most twice—once when entering the window and once when leaving.

This method generalizes well when the character set is larger than lowercase letters. Instead of fixed arrays, the frequency structure is stored in a map, making it flexible for arbitrary strings. It combines ideas from string processing and hash-based frequency tracking.

Recommended for interviews: The sliding window with character count is the most direct and commonly expected solution. It demonstrates understanding of fixed-window substring problems and achieves optimal O(n) time with constant space. Implementing the hashmap + two-pointer version also shows strong control over window management and frequency tracking. Interviewers usually accept either, but the fixed sliding window is typically the cleanest implementation.