Shortest Distance to a Character solution and explanation
Google
9 more videos on this problem
LeetCode Shortest Distance to a Character Solution Explained - JavaNick White · 11:14 · 11K views
Shortest Distance to a Character | Live Coding with Explanation | Leetcode #821Algorithms Made Easy · 5:41 · 5K views
Shortest Distance to a Character | Leetcode 821Coding Decoded · 12:37 · 2K views
Leetcode - Shortest Distance to a Character (Python)Timothy H Chang · 6:02 · 2K views
821. Shortest Distance to a Character | LEETCODE EASYcode Explainer · 6:32 · 1K views
Shortest Distance to a Character | LeetCode 821 | Coders CampCoders Camp · 14:56 · 718 views
Leetcode 821. Shortest Distance to a Character PythonTechZoo · 3:32 · 653 views
821. Shortest Distance to a Character (Leetcode Easy)Programming Live with Larry · 7:55 · 579 views
Leetcode 821 Shortest Distance to a Character - Facebook, Google Coding Interview QuestionAlgorithmicIQ · 26:44 · 316 views
821. Shortest Distance to a Character Leetcode problem/ Explanation + C++ codeCoding with U · 4:40 · 303 views
The problem
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.
Approach overview
Problem Overview: Given a string s and a target character c, compute the shortest distance from every index in the string to the nearest occurrence of c. The result is an integer array where each position stores the minimum distance to that character.
Approach 1: Brute Force Scan (O(n2) time, O(n) space)
The direct approach checks every index in the string and searches for the closest occurrence of c. For position i, iterate across the entire string and compute |i - j| whenever s[j] == c, keeping the minimum distance. Store that value in the result array. This method is straightforward and demonstrates the core idea of measuring absolute distances, but it repeatedly scans the string for every index. With n characters, the nested iteration leads to O(n2) time and O(n) space for the output array. Useful as a baseline but inefficient for large inputs.
Approach 2: Two Pass Approach (O(n) time, O(n) space)
The optimal solution observes that the closest occurrence of c must come either from the left side or the right side of a given index. Perform two linear scans of the string. In the first pass (left to right), track the most recent index where c appeared and compute the distance from that position. Store it in the result array. In the second pass (right to left), repeat the same logic but track the closest occurrence on the right and update the array using min(currentDistance, rightDistance). This guarantees the minimum distance from both directions. The algorithm processes each character twice, resulting in O(n) time and O(n) space.
This technique is essentially a directional scan over an array representation of the string. It avoids repeated searches and relies on simple arithmetic distance updates. The pattern appears frequently in problems involving nearest elements in a string or distance propagation across indices.
Recommended for interviews: Interviewers expect the two-pass linear scan. Starting with the brute force approach shows you understand the distance calculation, but quickly optimizing to the two-direction scan demonstrates strong problem-solving skills. The optimized approach uses constant work per index and resembles classic two pointers-style directional traversal patterns.
Approach 1: Two Pass Approach
This approach involves two passe through the string:
- First Pass: Traverse the string from left to right, keeping track of the most recent index of character
c. Calculate the distance from the current index to this recentc. - Second Pass: Traverse from right to left, updating the distances with the minimum between the current distance and the new distance to the closest
cfound on this traversal.
This ensures each element in the result is the minimum distance to any occurrence of c.
def shortestToChar(s: str, c: str) -> list:
n = len(s)
result = [0] * n
prev = float('-inf')
# First pass - left to right
for i in range(n):
if s[i] == c:
prev = i
result[i] = i - prev
# Second pass - right to left
prev = float('inf')
for i in range(n - 1, -1, -1):
if s[i] == c:
prev = i
result[i] = min(result[i], prev - i)
return resultimport java.util.*;
class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] result = new int[n];
int prev = -n;
// Left to right
for (int i = 0; i < n; i++) {
if (s.charAt(i) == c) prev = i;
result[i] = i - prev;
}
// Right to left
for (int i = n - 1, prev = 2 * n; i >= 0; i--) {
if (s.charAt(i) == c) prev = i;
result[i] = Math.min(result[i], prev - i);
}
return result;
}
}#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> shortestToChar(string s, char c) {
int n = s.size();
vector<int> result(n, n);
int prev = -n;
// Left to right
for (int i = 0; i < n; ++i) {
if (s[i] == c) prev = i;
result[i] = i - prev;
}
// Right to left
for (int i = n - 1, prev = 2 * n; i >= 0; --i) {
if (s[i] == c) prev = i;
result[i] = min(result[i], prev - i);
}
return result;
}var shortestToChar = function(s, c) {
const result = new Array(s.length).fill(0);
let prev = -Infinity;
// Left to right
for (let i = 0; i < s.length; i++) {
if (s[i] === c) prev = i;
result[i] = i - prev;
}
// Right to left
prev = Infinity;
for (let i = s.length - 1; i >= 0; i--) {
if (s[i] === c) prev = i;
result[i] = Math.min(result[i], prev - i);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
int* shortestToChar(char* s, char c, int* returnSize) {
int len = strlen(s);
*returnSize = len;
int* result = (int*)malloc(len * sizeof(int));
int prev = -INT_MAX;
// First pass - left to right
for(int i = 0; i < len; i++) {
if (s[i] == c) {
prev = i;
}
result[i] = i - prev;
}
// Second pass - right to left
prev = INT_MAX;
for(int i = len - 1; i >= 0; i--) {
if (s[i] == c) {
prev = i;
}
result[i] = (result[i] < prev - i) ? result[i] : prev - i;
}
return result;
}using System;
public class Solution {
public int[] ShortestToChar(string s, char c) {
int n = s.Length;
int[] result = new int[n];
int prev = -n;
// Forward pass
for (int i = 0; i < n; i++) {
if (s[i] == c) prev = i;
result[i] = i - prev;
}
// Backward pass
for (int i = n - 1; i >= 0; i--) {
if (s[i] == c) prev = i;
result[i] = Math.Min(result[i], Math.Abs(i - prev));
}
return result;
}
}The Python solution initializes a result list of same length as s to store shortest distances. It computes distances moving from left to right, and corrects them while moving from right to left using the minimum distance found from a c on the right.
Time Complexity: O(n) as we iterate through the string twice, adjusting distances for each character.
Space Complexity: O(n) for the storage of the result list.
Approach 2: Default Approach
function shortestToChar(s: string, c: string): number[] {
const n = s.length;
const inf = 1 << 30;
const ans: number[] = new Array(n).fill(inf);
for (let i = 0, pre = -inf; i < n; ++i) {
if (s[i] === c) {
pre = i;
}
ans[i] = i - pre;
}
for (let i = n - 1, suf = inf; i >= 0; --i) {
if (s[i] === c) {
suf = i;
}
ans[i] = Math.min(ans[i], suf - i);
}
return ans;
}func shortestToChar(s string, c byte) []int {
n := len(s)
ans := make([]int, n)
const inf int = 1 << 30
pre := -inf
for i := range s {
if s[i] == c {
pre = i
}
ans[i] = i - pre
}
suf := inf
for i := n - 1; i >= 0; i-- {
if s[i] == c {
suf = i
}
ans[i] = min(ans[i], suf-i)
}
return ans
}impl Solution {
pub fn shortest_to_char(s: String, c: char) -> Vec<i32> {
let c = c as u8;
let s = s.as_bytes();
let n = s.len();
let mut res = vec![i32::MAX; n];
let mut pre = i32::MAX;
for i in 0..n {
if s[i] == c {
pre = i as i32;
}
res[i] = i32::abs((i as i32) - pre);
}
pre = i32::MAX;
for i in (0..n).rev() {
if s[i] == c {
pre = i as i32;
}
res[i] = res[i].min(i32::abs((i as i32) - pre));
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pass Approach | Time Complexity: Space Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n^2) | O(n) | Conceptual baseline or when explaining the naive solution first in interviews |
| Two Pass Approach | O(n) | O(n) | Optimal solution for production and coding interviews |
Frequently asked questions
Is Shortest Distance to a Character easy or hard?
Shortest Distance to a Character is classified as an Easy problem. The challenge is recognizing that the nearest target can come from either direction and solving it efficiently using two linear passes instead of repeated searches.
Shortest Distance to a Character Python/Java solution
The typical Python or Java implementation uses an integer array for results and two loops across the string. Each loop tracks the nearest occurrence of the target character and updates the minimum distance in O(n) time.
How to solve Shortest Distance to a Character in O(n)?
Perform two passes over the string. During the first pass (left to right), track the most recent index of the target character and compute the distance for each position. During the second pass (right to left), track the nearest occurrence on the right and update each index using the minimum of the two distances.
What is the best approach for Shortest Distance to a Character?
The two-pass linear scan is the best approach. Scan the string from left to right to compute distances from the closest left occurrence of the target character, then scan from right to left to update distances using the nearest right occurrence. This guarantees the minimum distance in O(n) time and O(n) space.
Is Shortest Distance to a Character asked at Google/Amazon/Meta?
Variants of nearest-element or distance-to-target problems appear in interviews at companies like Amazon, Google, and Meta. They test your ability to optimize from a brute-force scan to a linear-time directional pass solution.
What data structure is used in Shortest Distance to a Character?
The problem mainly uses an array to store distances and simple integer variables to track the last seen index of the target character. The algorithm relies on sequential scans rather than complex data structures.
What is the time complexity of Shortest Distance to a Character?
The optimal solution runs in O(n) time where n is the length of the string. The algorithm performs two linear passes over the string. Space complexity is O(n) for the output distance array.