What is the best approach for Shortest Distance to a Character?

Two-pointer scanning with invariant tracking is optimal, performing left-to-right and right-to-left passes to ensure minimal distances.

How do I handle indices before the first or after the last occurrence of the target character?

Initialize distances with large values and update only when a target character has been seen in the scan, correcting in the opposite direction pass.

Can this problem be solved in O(n) time?

Yes, using the two-pass scan ensures each character is visited twice, giving O(n) time complexity.

Does the approach handle ties automatically?

Yes, since we take the minimum distance from left and right passes, ties are resolved correctly without extra comparisons.

Is extra space needed besides the output array?

No significant extra space is needed; only variables to track the last seen target index are required.

#821

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

字符的最短距离

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它最近的字符 c 的距离。两个下标 i 和 j 之间的距离为 abs(i…

数组双指针字符串

题目描述

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它最近的字符 c 的距离。

两个下标 i 和 j 之间的距离为 abs(i - j) ，其中 abs 是绝对值函数。

示例 1：

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

示例 2：

输入：s = "aaab", c = "b"
输出：[3,2,1,0]

提示：

1 <= s.length <= 10⁴
s[i] 和 c 均为小写英文字母
题目数据保证 c 在 s 中至少出现一次

lightbulb

解题思路

方法一：两次遍历

我们先创建一个长度为 $n$ 的答案数组 $ans$ 。

接下来，我们从左到右遍历字符串 $s$ ，记录最近出现的字符 $c$ 的位置 $pre$ ，那么对于位置 $i$ ，答案就是 $i - pre$ ，即 $ans[i] = i - pre$ 。

然后，我们从右到左遍历字符串 $s$ ，记录最近出现的字符 $c$ 的位置 $suf$ ，那么对于位置 $i$ ，答案就是 $suf - i$ ，即 $ans[i] = \min(ans[i], suf - i)$ 。

最后返回答案数组 $ans$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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 ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each character is visited twice (left-to-right and right-to-left). Space complexity is O(n) for the output array; additional space is O(1) for tracking indices. This pattern avoids nested loops and redundant distance computations.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Notice if the candidate attempts nested loops instead of two-pass scanning.
question_mark
Check if they correctly handle indices before the first and after the last occurrence of c.
question_mark
Observe whether they maintain an invariant for the nearest target character index.

warning

常见陷阱

外企场景

error
Using a brute-force approach that computes distances to all occurrences for each index, causing O(n^2) time.
error
Failing to update distances correctly in the second (right-to-left) pass, leading to incorrect minimal distances.
error
Not handling edge indices properly when the target character has not yet appeared in the scan.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute shortest distances to multiple target characters simultaneously, extending the invariant tracking.
arrow_right_alt
Return the indices of the closest occurrence instead of distances, requiring minor modification to the scan.
arrow_right_alt
Handle a dynamic string where characters can be added or removed, updating distances incrementally.

help

常见问题

外企场景

继续练习

#809 情感丰富的文字 #942 增减字符串匹配 #1023 驼峰式匹配