Shortest Distance to a Character
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to iterate through each character of the string. For each character, we perform another full scan of the string to find the closest occurrence of the target character c.
Algorithm
- Initialize an integer array
answerwith the same length ass. - Loop through each index
ifrom0tos.length() - 1. - Inside the loop, initialize
minDistancetoInteger.MAX_VALUE. - Start a nested loop for each index
jfrom0tos.length() - 1. - If
s.charAt(j)is equal toc, updateminDistancewithMath.min(minDistance, Math.abs(i - j)). - After the inner loop, set
answer[i] = minDistance. - Return the
answerarray.
Walkthrough
For every index i in the string s, we initialize a minimum distance to a very large value. Then, we iterate through the entire string again with an index j. If the character at index j is the target character c, we calculate the distance abs(i - j) and update our minimum distance if this new distance is smaller. After checking all j's for a given i, the resulting minimum distance is stored in our answer array at index i.
class Solution { public int[] shortestToChar(String s, char c) { int n = s.length(); int[] answer = new int[n]; for (int i = 0; i < n; i++) { int minDistance = Integer.MAX_VALUE; for (int j = 0; j < n; j++) { if (s.charAt(j) == c) { minDistance = Math.min(minDistance, Math.abs(i - j)); } } answer[i] = minDistance; } return answer; }}Complexity
Time
O(N^2), where N is the length of the string `s`. For each of the N characters, we iterate through the entire string again, leading to a quadratic time complexity.
Space
O(N) for the output array `answer`. If the output array is not considered, the space complexity is O(1).
Trade-offs
Pros
Very simple to conceptualize and implement.
Cons
Highly inefficient and will likely result in a 'Time Limit Exceeded' error for larger inputs as specified in the constraints.
To improve upon the brute-force method, we can avoid repeatedly scanning the string for the character c. We can first iterate through the string once to find all indices where c appears and store them in a list. Then, for each index i of the string, we find the minimum distance to an index in our pre-computed list.
Algorithm
- Create a list
c_indicesto store indices of characterc. - Iterate through
sand populatec_indices. - Initialize an integer array
answerwith the same length ass. - Loop through each index
ifrom0tos.length() - 1. - For each
i, perform a binary search onc_indicesto find the closest occurrence ofc. - The closest
cwill be at the insertion point or the element before it. Calculate the distances to both and take the minimum. - Store this minimum distance in
answer[i]. - Return the
answerarray.
Walkthrough
First, we create a list, say c_indices, and populate it with all the indices where the character c is found in the string s. Since we iterate from left to right, this list will be naturally sorted.
Next, we iterate through the string s from i = 0 to n-1. For each i, we need to find the index j in c_indices that minimizes abs(i - j). Since c_indices is sorted, we can use binary search to find the insertion point of i. The two candidates for the closest index will be the one at the insertion point and the one just before it. We calculate the distance to both and take the minimum.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int[] shortestToChar(String s, char c) { int n = s.length(); List<Integer> cIndices = new ArrayList<>(); for (int i = 0; i < n; i++) { if (s.charAt(i) == c) { cIndices.add(i); } } int[] answer = new int[n]; for (int i = 0; i < n; i++) { int insertionPoint = Collections.binarySearch(cIndices, i); if (insertionPoint >= 0) { answer[i] = 0; } else { insertionPoint = -(insertionPoint + 1); int dist1 = Integer.MAX_VALUE; if (insertionPoint < cIndices.size()) { dist1 = cIndices.get(insertionPoint) - i; } int dist2 = Integer.MAX_VALUE; if (insertionPoint > 0) { dist2 = i - cIndices.get(insertionPoint - 1); } answer[i] = Math.min(dist1, dist2); } } return answer; }}Complexity
Time
O(N log K), where N is the length of `s` and K is the number of occurrences of `c`. The initial scan to find indices is O(N). Then, for each of the N indices, we perform a binary search on the list of K indices, which takes O(log K) time.
Space
O(K) to store the `c_indices` list, plus O(N) for the output array. In the worst case, K can be N, so the space complexity is O(N).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Guaranteed to pass within the time limits.
Cons
Slightly more complex to implement due to the binary search logic.
Not the most optimal solution in terms of time complexity.
The most optimal solution involves making two passes over the string. The first pass calculates the distances from each character to the nearest c on its left. The second pass calculates the distances to the nearest c on its right. The final answer for each position is the minimum of these two calculated distances.
Algorithm
- Initialize an integer array
answerof sizenand a position variablepos = -n. - First Pass (Left to Right): Iterate
ifrom0ton-1. - If
s.charAt(i) == c, updatepos = i. - Set
answer[i] = i - pos. - Second Pass (Right to Left): Reset
posto a large value like2*n. - Iterate
ifromn-1down to0. - If
s.charAt(i) == c, updatepos = i. - Update
answer[i] = Math.min(answer[i], pos - i). - Return the
answerarray.
Walkthrough
We can solve this problem in linear time by breaking it down into two simpler problems:
- Find the distance to the nearest
con the left for each character. - Find the distance to the nearest
con the right for each character. The final answer is the minimum of these two values.
Pass 1 (Left to Right):
We initialize a result array ans and a variable pos to track the last seen index of c (initialized to a very small number, e.g., -n). We iterate from left to right. If s[i] == c, we update pos = i. For each i, we set ans[i] = i - pos.
Pass 2 (Right to Left):
We now iterate from right to left. We reset pos to a very large number (e.g., 2*n). If s[i] == c, we update pos = i. For each i, we update ans[i] by taking min(ans[i], pos - i). This second pass effectively considers the nearest c from the right.
After both passes, ans will contain the shortest distance for each character.
class Solution { public int[] shortestToChar(String s, char c) { int n = s.length(); int[] answer = new int[n]; int pos = -n; // Initialize to a position far to the left // First pass: left to right for (int i = 0; i < n; i++) { if (s.charAt(i) == c) { pos = i; } answer[i] = i - pos; } // Second pass: right to left pos = n * 2; // Initialize to a position far to the right for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == c) { pos = i; } answer[i] = Math.min(answer[i], pos - i); } return answer; }}Complexity
Time
O(N), where N is the length of the string `s`. We perform two separate linear scans of the string, which results in O(N) + O(N) = O(N) time.
Space
O(N) for the output array `answer`. Excluding the output array, the space complexity is O(1) as we only use a few variables.
Trade-offs
Pros
Optimal time complexity of O(N).
Simple to implement and understand.
Efficient in terms of space, using only constant extra space (excluding the output array).
Cons
Requires two passes over the input string, which might be a slight disadvantage in scenarios where data can only be streamed once, though not applicable here.
Solutions
Solution
class Solution {public int[] shortestToChar(String s, char c) { int n = s.length(); int[] ans = new int[n]; final int inf = 1 << 30; Arrays.fill(ans, inf); for (int i = 0, pre = -inf; i < n; ++i) { if (s.charAt(i) == c) { pre = i; } ans[i] = Math.min(ans[i], i - pre); } for (int i = n - 1, suf = inf; i >= 0; --i) { if (s.charAt(i) == c) { suf = i; } ans[i] = Math.min(ans[i], suf - i); } return ans; }}class Solution {public: vector<int> shortestToChar(string s, char c) { int n = s.size(); const int inf = 1 << 30; vector<int> ans(n, inf); for (int i = 0, pre = -inf; i < n; ++i) { if (s[i] == c) { pre = i; } ans[i] = min(ans[i], i - pre); } for (int i = n - 1, suf = inf; ~i; --i) { if (s[i] == c) { suf = i; } ans[i] = min(ans[i], suf - i); } return ans; }};class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: n = len(s) ans = [n] * n pre = - inf for i, ch in enumerate(s): if ch == c: pre = i ans[i] = min(ans[i], i - pre) suf = inf for i in range(n - 1, - 1, - 1): if s[i] == c: suf = i ans[i] = min(ans[i], suf - i) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.