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
sconsisting of lowercase English letters. - A character
cwhich is guaranteed to occur at least once ins.
Outputs:
- An array of integers where each integer represents the shortest distance from the corresponding index in
sto the closest occurrence ofc.
Implicit Constraints or Tricky Edge Cases:
- The string can be up to 10,000 characters long.
- The character
cis guaranteed to exist in the string, so we don’t need to handle cases wherecis 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:
- First pass from left to right: Track the distance from each character to the nearest
cencountered so far. - Second pass from right to left: Update the distances by considering the closest
cencountered in this direction, ensuring that we get the minimum distance.
This approach reduces the time complexity to O(n).
Approach
- Initialize an array
answerof the same length ass, filled with a large number (e.g., infinity) to represent initial distances. - Traverse the string from left to right:
- Keep track of the last seen index of
c. - For each character, update its distance in
answerbased on the distance to the last seenc.
- Keep track of the last seen index of
- Traverse the string from right to left:
- Again, keep track of the last seen index of
c. - Update the distances in
answerby considering the minimum distance between the current value and the distance to the last seencfrom this direction.
- Again, keep track of the last seen index of
- Return the
answerarray.
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
answerarray.
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 alreadyc. cappears only once at the start or end of the string: The distances for indices before or aftercwill correctly reflect their distance toc.
The solution provided is correct, efficient, and clear. It handles all edge cases and adheres to the constraints given in the problem statement.