We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Distance to a Character

Difficulty: Easy

Problem Description

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.

Key Insights

  • We need to find the closest occurrences of a specific character in a string for each index.
  • The distance is calculated as the absolute difference between indices.
  • We can compute the distances in a single pass from left to right and then from right to left to ensure we capture the closest occurrences efficiently.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a two-pass approach with an array to store the distances. In the first pass, we iterate through the string from left to right, maintaining the last seen index of the character c. We calculate the distances based on this index. In the second pass, we iterate from right to left, updating the distances to ensure we find the minimum distance to the closest occurrence of c. This approach ensures that we efficiently calculate the required distances using linear time complexity.

Code Solutions

def shortestToChar(s: str, c: str) -> List[int]:
    n = len(s)
    answer = [0] * n
    last_position = float('-inf')

    # First pass: left to right
    for i in range(n):
        if s[i] == c:
            last_position = i
        answer[i] = abs(i - last_position)

    last_position = float('inf')

    # Second pass: right to left
    for i in range(n - 1, -1, -1):
        if s[i] == c:
            last_position = i
        answer[i] = min(answer[i], abs(i - last_position))

    return answer
← Back to All Questions