Difficulty: Easy | Acceptance: 72.80% | Paid: No Topics: Array, Two Pointers, String
Given a string s and a character c that appears 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).
- Examples
- Constraints
- Brute Force
- Two Pass
- BFS from All Occurrences
Examples
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.
Example 2
Input: s = "aaab", c = "b"
Output: [3,2,1,0]
Explanation: The character 'b' appears at index 3.
Constraints
1 <= s.length <= 10⁴
s[i] and c are lowercase English letters.
c is guaranteed to appear at least once in s.
Brute Force
Intuition For each position in the string, scan through all positions to find the minimum distance to the target character.
Steps
- Iterate through each index of the string
- For each index, scan through all positions of the string
- Track the minimum distance to any occurrence of character c
- Store the minimum distance in the result array
class Solution:
def shortestToChar(self, s: str, c: str) -> list[int]:
n = len(s)
result = []
for i in range(n):
min_dist = float('inf')
for j in range(n):
if s[j] == c:
min_dist = min(min_dist, abs(i - j))
result.append(min_dist)
return result
Complexity
- Time: O(n²)
- Space: O(n)
- Notes: Simple but inefficient for large inputs
Two Pass
Intuition Make two passes through the string: left-to-right to find distances to the nearest c on the left, and right-to-left to find distances to the nearest c on the right, then take the minimum.
Steps
- First pass (left to right): track the most recent occurrence of c and compute distance from the left
- Second pass (right to left): track the most recent occurrence of c and compute distance from the right
- For each position, take the minimum of left and right distances
class Solution:
def shortestToChar(self, s: str, c: str) -> list[int]:
n = len(s)
result = [float('inf')] * n
# Left to right pass
prev = -n
for i in range(n):
if s[i] == c:
prev = i
result[i] = i - prev
# Right to left pass
prev = 2 * n
for i in range(n - 1, -1, -1):
if s[i] == c:
prev = i
result[i] = min(result[i], prev - i)
return result
Complexity
- Time: O(n)
- Space: O(n)
- Notes: Optimal solution with linear time complexity
BFS from All Occurrences
Intuition Treat this as a shortest path problem where all occurrences of c are starting points with distance 0, and we expand outward using BFS.
Steps
- Initialize result array with -1 (unvisited)
- Add all positions of character c to queue with distance 0
- Perform BFS, expanding to adjacent positions
- For each unvisited neighbor, set its distance to current distance + 1
from collections import deque
class Solution:
def shortestToChar(self, s: str, c: str) -> list[int]:
n = len(s)
result = [-1] * n
queue = deque()
# Initialize queue with all positions of c
for i, ch in enumerate(s):
if ch == c:
result[i] = 0
queue.append(i)
# BFS
directions = [-1, 1]
while queue:
curr = queue.popleft()
for d in directions:
nxt = curr + d
if 0 <= nxt < n and result[nxt] == -1:
result[nxt] = result[curr] + 1
queue.append(nxt)
return result
Complexity
- Time: O(n)
- Space: O(n)
- Notes: Useful pattern for multi-source shortest path problems