Introduction

In this blog post, we will explore how to solve the LeetCode problem "438" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: 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". Example 2: 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". Constraints: 1 <= s.length, p.length <= 3 * 104 s and p consist of lowercase English letters.

Explanation

Here's an efficient solution to find anagrams in a string, along with explanations:

• Sliding Window and Character Frequency Counting: The core idea is to use a sliding window of the same length as string p to traverse string s. For each window, we compare the character frequencies within the window to the character frequencies of p. If the frequencies match, we have found an anagram.

• Frequency Array Optimization: Instead of creating substrings and sorting them for comparison or using dictionaries, we maintain frequency arrays (or hashmaps). One array stores the character frequencies of p, and another stores the frequencies of the current window in s. This allows for O(1) comparison of the frequencies. We update the window's frequency array efficiently as the window slides.

• Efficient Comparison: We compare the frequency arrays directly. If they are equal, it means the current window is an anagram of p, and we add the starting index of the window to the result list.

• Runtime Complexity & Storage Complexity: O(n), where n is the length of string s, and O(1), because the size of frequency array is constant (26).

Code

    def findAnagrams(s: str, p: str) -> list[int]:
    """
    Finds all the start indices of p's anagrams in s.

    Args:
        s: The string to search in.
        p: The string to find anagrams of.

    Returns:
        A list of the start indices of p's anagrams in s.
    """

    n = len(s)
    m = len(p)
    if m > n:
        return []

    p_freq = [0] * 26
    s_freq = [0] * 26
    result = []

    # Initialize frequency arrays for p and the first window of s
    for i in range(m):
        p_freq[ord(p[i]) - ord('a')] += 1
        s_freq[ord(s[i]) - ord('a')] += 1

    # Slide the window through s
    for i in range(n - m + 1):
        if s_freq == p_freq:
            result.append(i)

        # Update the frequency array for the next window
        if i < n - m:
            s_freq[ord(s[i]) - ord('a')] -= 1
            s_freq[ord(s[i + m]) - ord('a')] += 1

    return result