LeetCode 821 - Shortest Distance to a Character

LeetCode Problem 821

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, String

Solution

Problem Understanding

The problem gives us a string s and a target character c. For every index in the string, we must compute the distance to the nearest occurrence of c.

The distance between two indices is defined as:

$$|i - j|$$

where i is the current index and j is the index of some occurrence of c.

The result should be an integer array where:

• answer[i] represents the minimum distance from index i to any occurrence of character c
• the returned array must have the same length as the string

For example, if:

s = "loveleetcode"
c = "e"

then the character 'e' appears at indices:

3, 5, 6, 11

For index 0, the nearest 'e' is at index 3, so the distance is:

abs(0 - 3) = 3

For index 4, there are two equally close 'e' characters at indices 3 and 5, both with distance 1.

The constraints are relatively small:

• 1 <= s.length <= 10^4
• all characters are lowercase English letters
• c is guaranteed to appear at least once

The guarantee that c appears at least once is important because it means we never need to handle an impossible case where no valid distance exists.

There are several edge cases that are important to recognize early:

• The target character may appear only once
• The target character may appear at the beginning or end of the string
• Consecutive occurrences of c may exist
• Every character in the string could be equal to c
• Distances must always be computed relative to the nearest occurrence, not just the first or last occurrence

A naive implementation can easily fail if it only scans in one direction because the closest occurrence could be either to the left or to the right.

Approaches

Brute Force Approach

The most straightforward solution is to compute the answer for each position independently.

For every index i in the string:

1. Iterate through the entire string
2. Find every occurrence of c
3. Compute the distance from i to each occurrence
4. Keep the minimum distance

This works because it explicitly checks all possible target positions and chooses the smallest distance.

For example:

s = "aaab"
c = "b"

For index 0, we scan the whole string and find 'b' at index 3:

abs(0 - 3) = 3

This produces the correct result, but it is inefficient because for every character we scan the entire string again.

If the string length is n, then:

• Outer loop runs n times
• Inner loop also runs n times

This gives a time complexity of:

$$O(n^2)$$

Although 10^4 is not extremely large, an O(n^2) solution is unnecessary here because a more efficient linear solution exists.

Optimal Two Pass Approach

The key observation is that the nearest occurrence of c can come from either:

• the closest occurrence on the left
• the closest occurrence on the right

Instead of repeatedly searching the entire string, we can process the string twice:

1. Left to right
2. Right to left

During the left-to-right pass:

• keep track of the most recent occurrence of c
• compute distances to the closest c on the left

During the right-to-left pass:

• keep track of the nearest occurrence of c on the right

• update each answer with the minimum of:

• existing left distance

• right distance

This works because every closest occurrence must lie either to the left or the right of the current position.

Since each pass touches every character once, the total runtime becomes linear.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) excluding output	Checks every occurrence of c for every index
Optimal	O(n)	O(1) excluding output	Uses two directional passes to compute nearest distances

Algorithm Walkthrough

Optimal Two Pass Algorithm

1. Create a result array answer of size n.

This array will eventually store the minimum distance for every index. 2. Perform a left-to-right pass.

Maintain a variable previous_position representing the most recent index where character c appeared.

Initially, set it to a very large negative number so that positions before the first occurrence produce large distances. 3. For each index i from left to right:

• If s[i] == c, update previous_position = i
• Compute:

i - previous_position

• Store this value in answer[i]

At this point, answer[i] represents the distance to the nearest c on the left. 4. Perform a right-to-left pass.

Maintain another variable next_position representing the closest occurrence of c on the right.

Initially, set it to a very large positive number. 5. For each index i from right to left:

• If s[i] == c, update next_position = i
• Compute:

next_position - i

• Update:

answer[i] = min(answer[i], next_position - i)

Now answer[i] contains the minimum distance from either side. 6. Return the completed answer array.

Why it works

After the first pass, every index knows the distance to the nearest occurrence of c on its left side.

After the second pass, every index also considers the nearest occurrence on its right side.

Since the nearest occurrence of c must lie either to the left or right, taking the minimum of these two distances guarantees the correct answer.

Python Solution

from typing import List

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        answer = [0] * n

        previous_position = -n

        # Left-to-right pass
        for i in range(n):
            if s[i] == c:
                previous_position = i

            answer[i] = i - previous_position

        next_position = 2 * n

        # Right-to-left pass
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                next_position = i

            answer[i] = min(answer[i], next_position - i)

        return answer

The implementation begins by initializing the result array and storing the string length.

The variable previous_position tracks the most recent occurrence of c while scanning from left to right. Initially it is set to -n, which behaves like a very distant occurrence before the string starts.

During the first pass:

• when the current character equals c, we update previous_position
• otherwise we compute the distance from the current index to the nearest occurrence on the left

After this pass, each element stores the shortest left-side distance.

The second pass scans from right to left using next_position, which tracks the closest occurrence of c on the right.

For every index:

• compute the right-side distance
• take the minimum between the existing left-side distance and the new right-side distance

At the end, the array contains the shortest possible distances.

Go Solution

func shortestToChar(s string, c byte) []int {
	n := len(s)
	answer := make([]int, n)

	previousPosition := -n

	// Left-to-right pass
	for i := 0; i < n; i++ {
		if s[i] == c {
			previousPosition = i
		}

		answer[i] = i - previousPosition
	}

	nextPosition := 2 * n

	// Right-to-left pass
	for i := n - 1; i >= 0; i-- {
		if s[i] == c {
			nextPosition = i
		}

		rightDistance := nextPosition - i

		if rightDistance < answer[i] {
			answer[i] = rightDistance
		}
	}

	return answer
}

The Go implementation follows exactly the same algorithmic structure as the Python version.

Some Go-specific details are worth noting:

• Strings in Go are byte slices, so indexing with s[i] directly returns a byte
• The target character is given as byte
• make([]int, n) initializes the result slice
• Go does not provide a built-in min function for integers, so we compare values manually

No integer overflow concerns exist because the maximum string length is only 10^4.

Worked Examples

Example 1

s = "loveleetcode"
c = "e"

Target positions:

3, 5, 6, 11

Left-to-Right Pass

Index	Character	Previous e	Distance	Answer
0	l	-12	12	12
1	o	-12	13	13
2	v	-12	14	14
3	e	3	0	0
4	l	3	1	1
5	e	5	0	0
6	e	6	0	0
7	t	6	1	1
8	c	6	2	2
9	o	6	3	3
10	d	6	4	4
11	e	11	0	0

Intermediate result:

[12,13,14,0,1,0,0,1,2,3,4,0]

Right-to-Left Pass

Index	Character	Next e	Right Distance	Final Answer
11	e	11	0	0
10	d	11	1	1
9	o	11	2	2
8	c	11	3	2
7	t	11	4	1
6	e	6	0	0
5	e	5	0	0
4	l	5	1	1
3	e	3	0	0
2	v	3	1	1
1	o	3	2	2
0	l	3	3	3

Final result:

[3,2,1,0,1,0,0,1,2,2,1,0]

Example 2

s = "aaab"
c = "b"

Left-to-Right Pass

Index	Character	Previous b	Distance
0	a	-4	4
1	a	-4	5
2	a	-4	6
3	b	3	0

Intermediate result:

[4,5,6,0]

Right-to-Left Pass

Index	Character	Next b	Right Distance	Final
3	b	3	0	0
2	a	3	1	1
1	a	3	2	2
0	a	3	3	3

Final result:

[3,2,1,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two linear scans across the string
Space	O(1) excluding output	Only a few variables are used besides the result array

The algorithm processes the string twice, once from left to right and once from right to left. Each pass touches every character exactly once, giving a total linear runtime.

The only extra memory used is a handful of integer variables. The output array itself is required by the problem and is not counted as auxiliary space.

Test Cases

from typing import List

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        answer = [0] * n

        previous_position = -n

        for i in range(n):
            if s[i] == c:
                previous_position = i

            answer[i] = i - previous_position

        next_position = 2 * n

        for i in range(n - 1, -1, -1):
            if s[i] == c:
                next_position = i

            answer[i] = min(answer[i], next_position - i)

        return answer

solution = Solution()

# Provided example
assert solution.shortestToChar("loveleetcode", "e") == [3,2,1,0,1,0,0,1,2,2,1,0]

# Single occurrence at end
assert solution.shortestToChar("aaab", "b") == [3,2,1,0]

# Single character string
assert solution.shortestToChar("a", "a") == [0]

# All characters equal target
assert solution.shortestToChar("aaaa", "a") == [0,0,0,0]

# Target at beginning
assert solution.shortestToChar("baaa", "b") == [0,1,2,3]

# Multiple consecutive targets
assert solution.shortestToChar("abbbba", "b") == [1,0,0,0,0,1]

# Target in middle
assert solution.shortestToChar("abcde", "c") == [2,1,0,1,2]

# Symmetric distances
assert solution.shortestToChar("ababa", "b") == [1,0,1,0,1]

# Long gap between targets
assert solution.shortestToChar("ahelloz", "h") == [1,0,1,2,3,4,5]

print("All tests passed.")

Test Summary

Test	Why
"loveleetcode", "e"	Validates standard multiple-occurrence behavior
"aaab", "b"	Tests single occurrence at end
"a", "a"	Smallest possible input
"aaaa", "a"	Every position already equals target
"baaa", "b"	Target located at beginning
"abbbba", "b"	Consecutive target characters
"abcde", "c"	Target in center with symmetric distances
"ababa", "b"	Alternating pattern
"ahelloz", "h"	Large increasing distance sequence

Edge Cases

Target Character Appears Only Once

A common source of bugs is assuming multiple occurrences exist. Consider:

s = "aaab"
c = "b"

Every distance must be measured relative to the same index. The two-pass algorithm handles this naturally because both passes eventually reference the single valid occurrence.

Target Character at the Beginning or End

Boundary positions often create off-by-one errors.

Example:

s = "baaa"
c = "b"

During the left-to-right pass, the first character immediately sets the closest position. During the right-to-left pass, distances are correctly preserved because the minimum operation keeps the smaller value.

Similarly, when the target is at the end, the right-to-left pass handles the distances correctly.

Consecutive Occurrences of the Target

Consider:

s = "abbbba"
c = "b"

A naive implementation may accidentally overwrite distances incorrectly when multiple adjacent targets exist.

In this solution, whenever s[i] == c, the current position becomes the newest nearest occurrence. Since the distance becomes zero at those indices, the surrounding positions automatically compute correctly in both directions.

Every Character Equals the Target

Example:

s = "aaaa"
c = "a"

Every index should produce distance 0.

Both passes continually update the nearest occurrence at every step, so every computed distance becomes zero immediately. This verifies that the implementation handles dense target distributions correctly.