Shortest Distance to a Character - Solution & Explanation
Problem Statement
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]andcare lowercase English letters.- It is guaranteed that
coccurs at least once ins.
Approach Overview
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.
Approach 1: Two Pass Approach
This approach involves two passe through the string:
- First Pass: Traverse the string from left to right, keeping track of the most recent index of character
c. Calculate the distance from the current index to this recentc. - Second Pass: Traverse from right to left, updating the distances with the minimum between the current distance and the new distance to the closest
cfound 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:
- In the first loop, traverse the string from left to right. If the character at the current index matches
c, updateprevto this index. Calculate the distance of the current index toprevand store it. - In the second loop, traverse from right to left. Update
prevwhenever again the charactercis found. Then compute the new distance to the closestcusing thisprevand update the result if necessary.
Complexity
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 2: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pass Approach | Time Complexity: Space Complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode Shortest Distance to a Character Solution Explained - Java • Nick White • 11,428 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Distance to a Character easy or hard?
Shortest Distance to a Character Python/Java solution
How to solve Shortest Distance to a Character in O(n)?
What is the best approach for Shortest Distance to a Character?
Is Shortest Distance to a Character asked at Google/Amazon/Meta?
What data structure is used in Shortest Distance to a Character?
What is the time complexity of Shortest Distance to a Character?
Ready to solve this problem?
Practice Shortest Distance to a Character with our built-in code editor and test cases.
Practice on FleetCode