Introduction

In this blog post, we will explore how to solve the LeetCode problem "3008" 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 <= 5 105 1 <= a.length, b.length <= 5 105 s, a, and b contain only lowercase English letters.

Explanation

Here's the approach:

• Find all occurrences: Find all starting indices of string a and string b in s.
• Check for beautiful indices: Iterate through the indices of a occurrences and for each, check if there is an index of b occurrence within the distance k.

• Store and sort: Store the beautiful indices in a set to avoid duplicates, and then convert to a sorted list.

• Runtime Complexity: O(s.length + a.length + b.length) - due to the efficient string matching and linear scans. Storage Complexity: O(s.length) - at most, we could store all indices as beautiful indices.

Code

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

    Args:
        s: The input string.
        a: The string a.
        b: The string b.
        k: The integer k.

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

    a_indices = []
    b_indices = []

    for i in range(len(s) - len(a) + 1):
        if s[i:i + len(a)] == a:
            a_indices.append(i)

    for i in range(len(s) - len(b) + 1):
        if s[i:i + len(b)] == b:
            b_indices.append(i)

    beautiful_indices_set = set()
    for i in a_indices:
        for j in b_indices:
            if abs(i - j) <= k:
                beautiful_indices_set.add(i)
                break

    return sorted(list(beautiful_indices_set))