LeetCode 821: Shortest Distance to a Character (Two-Pass Nearest-Target Scan)
LeetCode 821StringTwo PassToday we solve LeetCode 821 - Shortest Distance to a Character.
Source: https://leetcode.com/problems/shortest-distance-to-a-character/
English
Problem Summary
Given a string s and a character c that appears in s, return an array where each index stores the shortest distance from that position to any occurrence of c.
Key Insight
For each position, the nearest c is either on the left or on the right. So we can compute both directions with two linear passes and take the minimum.
Algorithm (Two Passes)
1) Left to right: track the last seen index of c, and set ans[i] = i - last when available.
2) Right to left: track the next seen index of c, and update ans[i] = min(ans[i], next - i).
3) Return ans.
Complexity Analysis
Time: O(n).
Space: O(n) for output array (extra auxiliary space O(1)).
Common Pitfalls
- Using only one pass: it misses closer matches on the opposite side.
- Incorrect sentinel initialization for unseen positions (use very small/large placeholders safely).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] ans = new int[n];
int prev = -n;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == c) {
prev = i;
}
ans[i] = i - prev;
}
prev = 2 * n;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) == c) {
prev = i;
}
ans[i] = Math.min(ans[i], prev - i);
}
return ans;
}
}
func shortestToChar(s string, c byte) []int {
n := len(s)
ans := make([]int, n)
prev := -n
for i := 0; i < n; i++ {
if s[i] == c {
prev = i
}
ans[i] = i - prev
}
prev = 2 * n
for i := n - 1; i >= 0; i-- {
if s[i] == c {
prev = i
}
if prev-i < ans[i] {
ans[i] = prev - i
}
}
return ans
}
class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int n = (int)s.size();
vector<int> ans(n);
int prev = -n;
for (int i = 0; i < n; ++i) {
if (s[i] == c) prev = i;
ans[i] = i - prev;
}
prev = 2 * n;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == c) prev = i;
ans[i] = min(ans[i], prev - i);
}
return ans;
}
};
class Solution:
def shortestToChar(self, s: str, c: str) -> list[int]:
n = len(s)
ans = [0] * n
prev = -n
for i, ch in enumerate(s):
if ch == c:
prev = i
ans[i] = i - prev
prev = 2 * n
for i in range(n - 1, -1, -1):
if s[i] == c:
prev = i
ans[i] = min(ans[i], prev - i)
return ans
var shortestToChar = function(s, c) {
const n = s.length;
const ans = new Array(n).fill(0);
let prev = -n;
for (let i = 0; i < n; i++) {
if (s[i] === c) prev = i;
ans[i] = i - prev;
}
prev = 2 * n;
for (let i = n - 1; i >= 0; i--) {
if (s[i] === c) prev = i;
ans[i] = Math.min(ans[i], prev - i);
}
return ans;
};
中文
题目概述
给定字符串 s 和其中一定出现的字符 c，返回数组 answer，其中 answer[i] 表示位置 i 到任意一个字符 c 的最短距离。
核心思路
每个位置最近的 c 只可能来自左侧或右侧，所以做两次线性扫描即可：一次处理“最近左侧 c”，一次处理“最近右侧 c”，最后取最小值。
算法步骤（双向扫描）
1）从左到右扫描，记录最近一次出现 c 的位置 prev，计算 i - prev。
2）从右到左扫描，记录右侧最近的 c 位置，更新为 min(当前值, prev - i)。
3）返回结果数组。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（结果数组），额外辅助空间为 O(1)。
常见陷阱
- 只做单向扫描会漏掉另一侧更近的 c。
- 未正确设置初始哨兵值，导致边界距离计算错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] ans = new int[n];
int prev = -n;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == c) {
prev = i;
}
ans[i] = i - prev;
}
prev = 2 * n;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) == c) {
prev = i;
}
ans[i] = Math.min(ans[i], prev - i);
}
return ans;
}
}
func shortestToChar(s string, c byte) []int {
n := len(s)
ans := make([]int, n)
prev := -n
for i := 0; i < n; i++ {
if s[i] == c {
prev = i
}
ans[i] = i - prev
}
prev = 2 * n
for i := n - 1; i >= 0; i-- {
if s[i] == c {
prev = i
}
if prev-i < ans[i] {
ans[i] = prev - i
}
}
return ans
}
class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int n = (int)s.size();
vector<int> ans(n);
int prev = -n;
for (int i = 0; i < n; ++i) {
if (s[i] == c) prev = i;
ans[i] = i - prev;
}
prev = 2 * n;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == c) prev = i;
ans[i] = min(ans[i], prev - i);
}
return ans;
}
};
class Solution:
def shortestToChar(self, s: str, c: str) -> list[int]:
n = len(s)
ans = [0] * n
prev = -n
for i, ch in enumerate(s):
if ch == c:
prev = i
ans[i] = i - prev
prev = 2 * n
for i in range(n - 1, -1, -1):
if s[i] == c:
prev = i
ans[i] = min(ans[i], prev - i)
return ans
var shortestToChar = function(s, c) {
const n = s.length;
const ans = new Array(n).fill(0);
let prev = -n;
for (let i = 0; i < n; i++) {
if (s[i] === c) prev = i;
ans[i] = i - prev;
}
prev = 2 * n;
for (let i = n - 1; i >= 0; i--) {
if (s[i] === c) prev = i;
ans[i] = Math.min(ans[i], prev - i);
}
return ans;
};
Comments