Introduction

In this blog post, we will explore how to solve the LeetCode problem "3006" 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

You are given a 0-indexed string s, a string a, a string b, and an integer k. An index i is beautiful if: 0 <= i <= s.length - a.length s[i..(i + a.length - 1)] == a There exists an index j such that: 0 <= j <= s.length - b.length s[j..(j + b.length - 1)] == b |j - i| <= k Return the array that contains beautiful indices in sorted order from smallest to largest. Example 1: Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15 Output: [16,33] Explanation: There are 2 beautiful indices: [16,33]. - The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15. - The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15. Thus we return [16,33] as the result. Example 2: Input: s = "abcd", a = "a", b = "a", k = 4 Output: [0] Explanation: There is 1 beautiful index: [0]. - The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4. Thus we return [0] as the result. Constraints: 1 <= k <= s.length <= 105 1 <= a.length, b.length <= 10 s, a, and b contain only lowercase English letters.

Explanation

Here's the breakdown of the solution:

• Identify potential beautiful indices: Find all starting indices of string a within string s. These are the potential beautiful indices.
• Identify indices of b: Find all starting indices of string b within string s.

• Check for proximity: For each potential beautiful index, check if there's an index of b within the distance k. If found, then the potential beautiful index is indeed beautiful.

• Runtime Complexity: O(n + m + p), where n is the length of s, m is the length of a, and p is the length of b. This is due to the linear search for occurrences of a and b and the linear scan to verify conditions. Storage Complexity: O(n), where n is the length of s. This is used to store the indices of a and b.

Code

    def beautifulIndices(s: str, a: str, b: str, k: int) -> list[int]:
    """
    Finds all beautiful indices in a string.

    Args:
        s: The string to search in.
        a: The first substring to look for.
        b: The second substring to look for.
        k: The maximum distance between indices.

    Returns:
        A list of beautiful indices, sorted in ascending order.
    """

    a_indices = []
    b_indices = []
    n = len(s)
    a_len = len(a)
    b_len = len(b)

    # Find all indices of 'a' in 's'
    for i in range(n - a_len + 1):
        if s[i:i + a_len] == a:
            a_indices.append(i)

    # Find all indices of 'b' in 's'
    for i in range(n - b_len + 1):
        if s[i:i + b_len] == b:
            b_indices.append(i)

    beautiful_indices = []
    for i in a_indices:
        found = False
        for j in b_indices:
            if abs(i - j) <= k:
                found = True
                break
        if found:
            beautiful_indices.append(i)

    return sorted(beautiful_indices)