Shortest Distance to a Character — Problem & Solution
Shortest Distance to a Character solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Shortest Distance to a Character is an easy coding problem on arrays, strings and two pointers, asked in Amazon, Google and Meta interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Two Pointers
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s and a character c that occurs in s, return an array of integers answer where answer[i] is the distance from index i to the closest occurrence of c.
The distance between indices i and j is abs(i - j).
Example 1
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Example 2
Input: s = "aaab", c = "b"
Output: [3,2,1,0]
Example 3
Input: s = "aa", c = "a"
Output: [0,0]
Constraints
1 <= s.length <= 40s consists of lowercase English letters.c occurs at least once in s.
Hints for Shortest Distance to a Character
Hint 1
Two sweeps beat computing every pairwise distance.
Hint 2
Left to right, track the most recent occurrence of
cand record the distance behind you.Hint 3
Right to left, track the next occurrence and keep the smaller of the two distances.
How to solve Shortest Distance to a Character
Two sweeps: left to right records the distance to the most recent c, right to left records the distance to the next c; keep the smaller.
Approach
- Sweep forward with
prev = -∞; oncsetprev = i; writeout[i] = i - prev. - Sweep backward with
prev = +∞; oncsetprev = i; writeout[i] = min(out[i], prev - i).
Why it works
The nearest occurrence of c to any index is either the closest one on its left or the closest one on its right, and each sweep computes one of those exactly.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- The sentinel for "none yet" must be far enough away that
i - prevexceeds any real distance.
Reference solution
Python
def shortestToChar(s: str, c: str):
n = len(s)
out = [0] * n
prev = -10000
for i in range(n):
if s[i] == c:
prev = i
out[i] = i - prev
prev = 10000
for i in range(n - 1, -1, -1):
if s[i] == c:
prev = i
out[i] = min(out[i], prev - i)
return outJava
public static int[] shortestToChar(String s, String c) {
int n = s.length();
char target = c.charAt(0);
int[] out = new int[n];
int prev = -10000;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == target) prev = i;
out[i] = i - prev;
}
prev = 10000;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) == target) prev = i;
out[i] = Math.min(out[i], prev - i);
}
return out;
}C++
vector<int> shortestToChar(string s, string c) {
int n = (int) s.size();
char target = c[0];
vector<int> out(n, 0);
int prev = -10000;
for (int i = 0; i < n; i++) {
if (s[i] == target) prev = i;
out[i] = i - prev;
}
prev = 10000;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == target) prev = i;
out[i] = min(out[i], prev - i);
}
return out;
}JavaScript
var shortestToChar = function(s, c) {
const n = s.length;
const out = new Array(n).fill(0);
let prev = -10000;
for (let i = 0; i < n; i++) {
if (s[i] === c) prev = i;
out[i] = i - prev;
}
prev = 10000;
for (let i = n - 1; i >= 0; i--) {
if (s[i] === c) prev = i;
if (prev - i < out[i]) out[i] = prev - i;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.