Shortest Distance to a Character

Shortest Distance to a Character

What is this problem about?

The Shortest Distance to a Character interview question gives you a string s and a character c that is guaranteed to appear at least once in s. For each position i, find the shortest distance to any occurrence of character c in the string. Return an array where each element is the minimum distance from that index to the nearest occurrence of c.

Why is this asked in interviews?

Microsoft, Amazon, Google, and Bloomberg ask this beginner-to-intermediate problem because it has an elegant two-pass solution. A single scan from left to right finds the nearest previous c, and a scan from right to left finds the nearest subsequent c. Taking the minimum of both gives the answer. It tests the "two-pass scan" pattern and understanding of how to propagate nearest-position information efficiently.

Algorithmic pattern used

The pattern is two-pass linear scan. Pass 1 (left to right): track the last seen position of c. For each index i, dist[i] = i - last_c_pos. Initialize last_c_pos to negative infinity. Pass 2 (right to left): track the next seen position of c. For each index i, dist[i] = min(dist[i], next_c_pos - i). Initialize next_c_pos to positive infinity. The final dist array has the minimum distance to any occurrence of c.

Example explanation

s = "loveleetcode", c = 'e'.

Occurrences of 'e': indices 3, 7, 8, 11.

Left-to-right pass (distance to nearest previous 'e'):

• Indices 0,1,2: infinity (no 'e' yet).
• Index 3 (e): distance 0.
• Indices 4,5,6: 1,2,3.
• Index 7 (e): 0. Index 8 (e): 0.
• Index 9,10: 1,2. Index 11: 0.

Right-to-left pass updates earlier indices:

• Index 0: min(∞, 3-0)=3. Index 1: min(∞, 2)=2. Index 2: min(∞, 1)=1.

Result: [3,2,1,0,1,2,2,1,0,1,0,1,0] (similar pattern).

Common mistakes candidates make

• Using a single pass and missing the nearest c in the other direction — always need both left and right passes.
• Initializing the first pass with 0 instead of infinity — positions before the first c should initially have very large distances.
• Off-by-one in distance computation — distance from index i to index j is abs(i - j), not abs(i - j) + 1.
• Modifying the distance array in the second pass without taking the minimum (using assignment instead of min()).

Interview preparation tip

For the Shortest Distance to a Character coding problem, the two-pointer array string interview pattern is the clean O(n) solution. The two-pass scan — left for "distance to previous c", right for "distance to next c" — avoids storing all positions. Google and Bloomberg interviewers use this as a warm-up. Practice the pattern: "pass forward to propagate left context, pass backward to propagate right context" — it generalizes to many "nearest element" problems like product of array except self and trapping rain water.