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.
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; }}Video 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.