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 <= 104s[i] and c are lowercase English letters.c occurs at least once in s.The goal of #821 Shortest Distance to a Character is to compute, for each index in a string, the distance to the nearest occurrence of a given character. A common and efficient idea is to track the closest positions of the target character while scanning the string.
A popular strategy uses two passes. First, iterate from left to right while keeping track of the most recent position of the target character. For each index, calculate the distance from that last seen position. Then perform a second pass from right to left, updating the distance using the closest occurrence from the right side.
This approach ensures every character considers the nearest occurrence from both directions without nested loops. Since each element is processed a constant number of times, the algorithm runs efficiently with O(n) time complexity and uses O(n) space for the result array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two-pass traversal (left-to-right and right-to-left) | O(n) | O(n) |
Nick White
This approach involves two passe through the string:
c. Calculate the distance from the current index to this recent c.c found on this traversal.This ensures each element in the result is the minimum distance to any occurrence of c.
Time Complexity: O(n), where n is the length of the string since we go through the string twice.
Space Complexity: O(1) additional space for variables, aside from the output array.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <limits.h>
5
This solution implements a two-pass approach. We first allocate an array of the same length as the input string to store our results. We use two loops:
c, update prev to this index. Calculate the distance of the current index to prev and store it.prev whenever again the character c is found. Then compute the new distance to the closest c using this prev and update the result if necessary.Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A single pass only captures the nearest occurrence from one direction. By scanning both left-to-right and right-to-left, we ensure that each index considers the closest target character from either side.
Yes, this type of problem is common in coding interviews because it tests string traversal, distance calculation, and efficient scanning techniques. Variations of this question may appear in interviews at major tech companies.
An array is typically used to store the distance for each index in the string. Along with the result array, a variable is maintained to track the most recent index of the target character during traversal.
The optimal approach uses two passes over the string. First scan from left to right to track the closest occurrence on the left, then scan from right to left to account for the nearest occurrence on the right. This ensures each position gets the minimum distance efficiently.