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.Problem Overview: Given a string s and a target character c, compute the shortest distance from every index in the string to the nearest occurrence of c. The result is an integer array where each position stores the minimum distance to that character.
Approach 1: Brute Force Scan (O(n2) time, O(n) space)
The direct approach checks every index in the string and searches for the closest occurrence of c. For position i, iterate across the entire string and compute |i - j| whenever s[j] == c, keeping the minimum distance. Store that value in the result array. This method is straightforward and demonstrates the core idea of measuring absolute distances, but it repeatedly scans the string for every index. With n characters, the nested iteration leads to O(n2) time and O(n) space for the output array. Useful as a baseline but inefficient for large inputs.
Approach 2: Two Pass Approach (O(n) time, O(n) space)
The optimal solution observes that the closest occurrence of c must come either from the left side or the right side of a given index. Perform two linear scans of the string. In the first pass (left to right), track the most recent index where c appeared and compute the distance from that position. Store it in the result array. In the second pass (right to left), repeat the same logic but track the closest occurrence on the right and update the array using min(currentDistance, rightDistance). This guarantees the minimum distance from both directions. The algorithm processes each character twice, resulting in O(n) time and O(n) space.
This technique is essentially a directional scan over an array representation of the string. It avoids repeated searches and relies on simple arithmetic distance updates. The pattern appears frequently in problems involving nearest elements in a string or distance propagation across indices.
Recommended for interviews: Interviewers expect the two-pass linear scan. Starting with the brute force approach shows you understand the distance calculation, but quickly optimizing to the two-direction scan demonstrates strong problem-solving skills. The optimized approach uses constant work per index and resembles classic two pointers-style directional traversal patterns.
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.
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.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.
| Approach | Complexity |
|---|---|
| Two Pass Approach | Time Complexity: Space Complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n^2) | O(n) | Conceptual baseline or when explaining the naive solution first in interviews |
| Two Pass Approach | O(n) | O(n) | Optimal solution for production and coding interviews |
LeetCode Shortest Distance to a Character Solution Explained - Java • Nick White • 11,357 views views
Watch 9 more video solutions →Practice Shortest Distance to a Character with our built-in code editor and test cases.
Practice on FleetCode