Domain 1EasyCORE

Shortest Distance to a Character

The problem requires us to find the shortest distance from each character in a string `s` to the closest occurrence of a specified character `c`. The output should be an array where each element corresponds to the distance for that index in the input string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 1

821. Shortest Distance to a Character

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 70.1%


Problem Breakdown

The problem requires us to find the shortest distance from each character in a string s to the closest occurrence of a specified character c. The output should be an array where each element corresponds to the distance for that index in the input string.

Inputs:

  • A string s consisting of lowercase English letters.
  • A character c which is guaranteed to occur at least once in s.

Outputs:

  • An array of integers where each integer represents the shortest distance from the corresponding index in s to the closest occurrence of c.

Implicit Constraints or Tricky Edge Cases:

  • The string can be up to 10,000 characters long.
  • The character c is guaranteed to exist in the string, so we don’t need to handle cases where c is not found.

Intuition

A brute-force approach would involve for each character in the string, searching through the entire string to find the closest occurrence of c. This would result in a time complexity of O(n^2), which is inefficient given the constraints.

The key insight is to leverage two passes over the string:

  1. First pass from left to right: Track the distance from each character to the nearest c encountered so far.
  2. Second pass from right to left: Update the distances by considering the closest c encountered in this direction, ensuring that we get the minimum distance.

This approach reduces the time complexity to O(n).

Approach

  1. Initialize an array answer of the same length as s, filled with a large number (e.g., infinity) to represent initial distances.
  2. Traverse the string from left to right:
    • Keep track of the last seen index of c.
    • For each character, update its distance in answer based on the distance to the last seen c.
  3. Traverse the string from right to left:
    • Again, keep track of the last seen index of c.
    • Update the distances in answer by considering the minimum distance between the current value and the distance to the last seen c from this direction.
  4. Return the answer array.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string s. We make two passes over the string, each taking linear time.
  • Space Complexity: O(n) for storing the answer array.

Solution

def shortestToChar(s: str, c: str) -> List[int]:
    n = len(s)
    answer = [float('inf')] * n
    
    # First pass from left to right
    last_seen_c = -n  # Initialize to a value outside the valid index range
    for i in range(n):
        if s[i] == c:
            last_seen_c = i
        answer[i] = min(answer[i], abs(i - last_seen_c))
    
    # Second pass from right to left
    last_seen_c = 2 * n  # Initialize to a value outside the valid index range
    for i in range(n - 1, -1, -1):
        if s[i] == c:
            last_seen_c = i
        answer[i] = min(answer[i], abs(i - last_seen_c))
    
    return answer

Edge Cases Handled

  • Single character string: The algorithm correctly handles strings of length 1.
  • All characters are the same as c: The distance for all indices will be 0, as each character is already c.
  • c appears only once at the start or end of the string: The distances for indices before or after c will correctly reflect their distance to c.

The solution provided is correct, efficient, and clear. It handles all edge cases and adheres to the constraints given in the problem statement.