#438

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Find All Anagrams in a String

Find all starting indices of p's anagrams in s using sliding window and hash table approach.

Problem Statement

Given two strings s and p, return all the start indices of p's anagrams in s. An anagram of p is any substring of s that contains the same characters as p, including repeated characters. You may return the answer in any order. The problem tests your ability to efficiently track and compare substring character frequencies.

You are tasked with solving this problem using an optimal approach. The challenge lies in managing the current window of characters and ensuring the character frequencies are updated efficiently. With input strings s and p, the solution must handle both long strings (up to 30,000 characters) while ensuring accuracy.

Examples

Example 1

Input: s = "cbaebabacd", p = "abc"

Output: [0,6]

The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2

Input: s = "abab", p = "ab"

Output: [0,1,2]

The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints

1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.

Solution Approach

Sliding Window Approach

The sliding window technique is the key to solving this problem. We slide a window of size equal to the length of p across s. As we move the window one character at a time, we update the frequencies of the characters within the window and compare them to the target string p. This minimizes the need for recalculating frequencies from scratch.

Hash Table for Frequency Counting

A hash table is used to track the character frequencies of p and the current window in s. As the window slides, we add characters entering the window and remove characters leaving it, adjusting the counts in the hash table. If the character frequencies in the window match those of p, we have found an anagram.

Efficient Window Management

To efficiently manage the sliding window, we maintain the window size fixed to the length of p. Whenever a new character enters the window or a character exits, the window's state is updated in constant time, allowing us to check for anagrams in linear time relative to the size of s.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n), where n is the length of s. This is because we only traverse the string s once, updating the frequency table in constant time for each character. The space complexity is O(k), where k is the size of the alphabet (26 for lowercase English letters). This is due to the hash table that stores frequency counts for the characters.

What Interviewers Usually Probe

The candidate should demonstrate understanding of sliding window technique and hash table usage.
Look for correct handling of window updates and frequency comparison.
The candidate should be able to explain the time and space complexity effectively.

Common Pitfalls or Variants

Common pitfalls

Incorrectly resizing the window, leading to missed or false positives for anagrams.
Not updating the hash table correctly when characters enter and exit the window.
Failing to recognize the importance of tracking frequencies in constant time to achieve linear time complexity.

Follow-up variants

What if the input strings contain uppercase letters as well? Adapt the hash table to handle both cases.
How would you handle edge cases where s is shorter than p?
Can the solution be optimized further for a scenario with a large number of unique characters?

FAQ

What is the primary technique used to solve 'Find All Anagrams in a String'?

The problem is solved using the sliding window technique combined with a hash table to track character frequencies.

How does the sliding window technique help in solving this problem?

The sliding window technique allows you to efficiently update the window of characters in s and check for anagrams in linear time without recalculating frequencies from scratch.

Can this problem be solved in less than O(n) time complexity?

No, achieving O(n) time complexity is the optimal solution for this problem. Any approach slower than O(n) would not be efficient enough for large inputs.

Why is a hash table used in 'Find All Anagrams in a String'?

A hash table is used to store the character frequencies of both the target string p and the current sliding window in s, enabling quick comparison and updates as the window slides.

What happens if the length of s is smaller than p in 'Find All Anagrams in a String'?

If the length of s is smaller than p, there are no possible anagrams, and the function should return an empty array.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        m, n = len(s), len(p)
        ans = []
        if m < n:
            return ans
        cnt1 = Counter(p)
        cnt2 = Counter(s[: n - 1])
        for i in range(n - 1, m):
            cnt2[s[i]] += 1
            if cnt1 == cnt2:
                ans.append(i - n + 1)
            cnt2[s[i - n + 1]] -= 1
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        m, n = len(s), len(p)
        ans = []
        if m < n:
            return ans
        cnt1 = Counter(p)
        cnt2 = Counter(s[: n - 1])
        for i in range(n - 1, m):
            cnt2[s[i]] += 1
            if cnt1 == cnt2:
                ans.append(i - n + 1)
            cnt2[s[i - n + 1]] -= 1
        return ans

Continue Practicing

#424 longest repeating character replacement #395 longest substring with at least k repeating characters #567 permutation in string