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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Distance to a Character

Number: 841

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a string s and a character c that is guaranteed to appear in s, return an array where each element at index i is the minimum distance from i to any occurrence of character c in s. The distance between two indices i and j is defined as abs(i - j).

Key Insights

  • The problem can be solved efficiently with two passes through the string.
  • In the first pass (left-to-right), track the distance from the last seen occurrence of c.
  • In the second pass (right-to-left), update the distance using the next occurrence of c.
  • This two-pass technique guarantees that every index gets the minimum distance from both directions.
  • The solution leverages constant additional space (apart from the output array) and linear time complexity.

Space and Time Complexity

Time Complexity: O(n) where n is the length of string s, as we iterate over the string twice. Space Complexity: O(n) for the output array storing the distances.

Solution

The approach involves scanning the string twice with two pointers:

  1. In the first left-to-right pass, initialize a variable to store the most recent index where character c was encountered. For each index, calculate the distance from the current index to that last seen index. If c hasn't been seen yet, we can simulate an infinitely large distance.
  2. In the second right-to-left pass, reinitialize a variable to track the next occurrence of c. Update the distance at each index to be the minimum of the existing distance and the distance from the next occurrence.
  3. This two-pass approach ensures that each index's distance reflects the nearest occurrence of c.

Code Solutions

# Python solution for Shortest Distance to a Character

def shortestToChar(s: str, c: str) -> list:
    n = len(s)
    distances = [0] * n  # Initialize result array
    
    # First pass: left-to-right
    prev_occurrence = float('-inf')
    for i in range(n):
        if s[i] == c:
            prev_occurrence = i  # Update last seen index of c
        distances[i] = i - prev_occurrence  # Calculate distance from last occurrence
    
    # Second pass: right-to-left
    next_occurrence = float('inf')
    for i in range(n - 1, -1, -1):
        if s[i] == c:
            next_occurrence = i  # Update next seen index of c
        # Update distance to be the minimum from left or right occurrences
        distances[i] = min(distances[i], next_occurrence - i)
    
    return distances

# Example usage:
# print(shortestToChar("loveleetcode", "e"))
← Back to All Questions