Abstract / Summary

Given a string and a character, find the shortest distance from each character in the string to the nearest occurrence of that character.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 73% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “shortest distance to a character” problem. It receives a string s and a target character c, and for each position in s it yields the distance to the nearest occurrence of c. The algorithm builds a list of marker positions that include sentinel values far outside the valid index range, then iterates through the string once, computing distances to the nearest markers on both sides. The use of a generator (yield) allows the result to be produced lazily, which can be advantageous when the caller consumes the output incrementally.

Key Steps

The first step creates a list called pos that contains three parts: a large negative sentinel, the indices of every occurrence of c in s, and a large positive sentinel. This construction guarantees that for any index i in the string there will always be a “previous” and a “next” marker to compare against, eliminating the need for explicit boundary checks inside the main loop.

pos = [ -99999999 ] + [ i for i in range(len(s)) if s[i] == c ] + [ +99999999 ]

A variable scan is initialized to 1. This variable points to the current “next” marker in the pos list. As the loop progresses, scan is advanced whenever the current index coincides with a marker, ensuring that the two markers used for distance calculations always bracket the current position.

scan = 1

The core loop iterates over each index i of the input string. For each i, two distances are computed: up is the absolute difference between i and the marker at pos[scan] (the next occurrence of c), while down is the absolute difference between i and the marker at pos[scan - 1] (the previous occurrence). The minimum of these two distances is the desired result for that position, and it is emitted via yield.

for i in range(len(s)):
    up   = abs(pos[scan    ] - i) # next occurrence
    down = abs(pos[scan - 1] - i) # previous occurrence
    if up == 0:
        scan += 1
    yield min(up, down)

The conditional if up == 0: detects when the current index i is exactly at a marker (i.e., s[i] == c). In that case the algorithm increments scan so that subsequent iterations will treat the next marker as the “next” occurrence, keeping the bracket correctly aligned.

Edge Cases Handled

The sentinel values -99999999 and +99999999 act as virtual markers placed far outside the range of valid indices. This design automatically handles cases where the target character appears only at the beginning or only at the end of the string. For example, when c occurs at index 0 and nowhere else, the “previous” marker for any index i > 0 will be the negative sentinel, but the distance to that sentinel is never chosen because the distance to the actual occurrence at index 0 will always be smaller. Conversely, when c appears only at the last index, the positive sentinel ensures that the “next” distance is never mistakenly selected.

Another edge condition is an empty string s. In that scenario the list comprehension that builds pos yields only the two sentinel values, and the loop body never executes because range(len(s)) is empty. The function therefore produces no output, which aligns with the expectation that there are no positions to compute distances for.

If the target character c does not appear in s at all, the list comprehension contributes no interior indices, leaving pos as [ -99999999, +99999999 ]. The loop still runs for each index, and the distances computed will be the absolute differences to the two far-away sentinels. Because both sentinels are symmetric and extremely distant, the minimum distance will be a large constant, effectively indicating the absence of c. This behavior is deterministic and avoids any index-out-of-range errors.

Performance Optimizations

The algorithm achieves linear time performance by scanning the string exactly once after the initial construction of the pos list. The list comprehension that gathers the positions of c runs in a single pass over s, and the subsequent loop processes each character without any nested iteration. By storing the positions of c in a pre-computed list, the code avoids repeated searches for the nearest occurrence during each iteration.

The use of sentinel values eliminates conditional branches that would otherwise be required to check whether a “previous” or “next” marker exists. This simplification reduces the number of runtime checks inside the hot loop, allowing the interpreter to execute the distance calculations more efficiently.

The variable scan moves monotonically forward through the pos list. Because it never resets or moves backward, each marker is examined at most once, which prevents redundant work. The conditional increment of scan occurs only when the current index matches a marker, a situation that happens exactly as many times as there are occurrences of c.

Finally, the function is implemented as a generator. By yielding each distance as soon as it is computed, the code avoids allocating an intermediate list of results. This lazy evaluation can lead to lower memory consumption, especially when the caller consumes the output incrementally or stops early. The generator also enables the caller to chain further processing steps without materializing the entire result set.

Imagine you are standing on a long path made of colorful blocks. Some of those blocks have a special star painted on them. Your job is to walk from the first block to the last one and count how many steps it takes to reach the nearest star.

To make this easier, imagine putting two giant invisible walls very far away, one at the beginning of the path and one at the end. These walls hold a marker for the star location. You start at the very first block and look at the nearest star to your left and the nearest star to your right. You pick the smallest number of steps between those two options.

As you walk forward one block at a time, you keep checking which star is closer. Sometimes, when you step directly onto a star, you stop looking at the one behind you and start looking for the next star further down the path. You write down the winner, which is the smallest number of steps, for every single block until you reach the very end. The result is a list of numbers that tells you exactly how close every block is to its favorite star.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Rust		Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim									C
	everthis			JS
	fartem							Ruby
	fengvyi	C++
	halfrost								Go
	JoshCrozier			JS
	Krazune	C++
	lkwq007		Python
	MacJim	C++
	ruoru						Rust
	suxrobGM					C#
	varunu28				Java
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
halfrost	Go
JoshCrozier	JavaScript
Krazune	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality