Introduction

In this blog post, we will explore how to solve the LeetCode problem "821" 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 a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s. The distance between two indices i and j is abs(i - j), where abs is the absolute value function. Example 1: Input: s = "loveleetcode", c = "e" Output: [3,2,1,0,1,0,0,1,2,2,1,0] Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed). The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3. The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2. For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1. The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2. Example 2: Input: s = "aaab", c = "b" Output: [3,2,1,0] Constraints: 1 <= s.length <= 104 s[i] and c are lowercase English letters. It is guaranteed that c occurs at least once in s.

Explanation

Here's an efficient solution to the problem, along with explanations:

• Two-Pass Approach: Iterate through the string from left to right, calculating the distance to the closest 'c' to the left. Then, iterate from right to left, updating the distances with the closest 'c' to the right. This ensures we find the absolute closest 'c' for each index.

• Initialization with Infinity: Initialize the distance array with infinity. This allows us to easily update the distances with smaller values during the two passes.

• Runtime Complexity: O(n), where n is the length of the string s. Storage Complexity: O(n) due to the answer array.

Code

    def shortest_to_char(s: str, c: str) -> list[int]:
    n = len(s)
    answer = [float('inf')] * n

    # Left to right pass
    closest = float('inf')
    for i in range(n):
        if s[i] == c:
            closest = 0
        else:
            closest += 1
        answer[i] = closest

    # Right to left pass
    closest = float('inf')
    for i in range(n - 1, -1, -1):
        if s[i] == c:
            closest = 0
        else:
            closest += 1
        answer[i] = min(answer[i], closest)

    return answer