algoadvance

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example

Input: s = "cbaebabacd", p = "abc" Output: [0, 6] Explanation: 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”.

Input: s = "abab", p = "ab" Output: [0, 1, 2] Explanation: 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”.

Clarifying Questions

1. What is the length of the input strings? Constraints typically mention that 1 <= s.length, p.length <= 3 * 10^4.

2. Are the strings case-sensitive? Yes, the problem involves lowercase English letters only.

3. Can s and p be empty? As per the problem statement, they cannot be empty since the minimum length is 1.

Strategy

1. Frequency Count: Utilize a frequency counter to count the occurrences of each character in p.
2. Sliding Window: Maintain a sliding window of the same size as p and slide across s to check each substring of size p for being an anagram.
3. Count Matching: Compare the frequency of characters in the current window to the frequency count of p.

Code

from collections import Counter

def findAnagrams(s, p):
    if len(p) > len(s):
        return []
    
    p_count = Counter(p)
    s_count = Counter()
    
    result = []
    window_size = len(p)
    
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        # Remove the character that's now outside the window
        if i >= window_size:
            if s_count[s[i - window_size]] == 1:
                del s_count[s[i - window_size]]
            else:
                s_count[s[i - window_size]] -= 1
        
        # Compare window with the pattern
        if s_count == p_count:
            result.append(i - window_size + 1)
    
    return result

# Example usage
s = "cbaebabacd"
p = "abc"
print(findAnagrams(s, p))  # Output: [0, 6]

s = "abab"
p = "ab"
print(findAnagrams(s, p))  # Output: [0, 1, 2]

Time Complexity

• Initialization: Creating the p_count Counter is O(M), where M is the length of p.
• Sliding Window Execution: We traverse the string s once which is O(N), where N is the length of s. Updating the counter for each character is O(1).
• Comparison: Checking if two Counters are equal takes O(1) if we assume the alphabet size is fixed (26 letters).

Overall, the time complexity is O(N + M), which is efficient for the given problem constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?