LeetCode 821: Shortest Distance to a Character

Problem Restatement

We are given a string s and a character c.

The character c appears at least once in s.

For every index i, we need to find the shortest distance from i to any index where s[index] == c.

The distance between two indices i and j is:

abs(i - j)

Return an array answer, where:

answer[i] = distance from i to the closest c

The official constraints say s has length at most 10^4, all characters are lowercase English letters, and c occurs at least once in s.

Input and Output

Examples

Example 1:

s = "loveleetcode"
c = "e"

The character "e" appears at indices:

3, 5, 6, 11

The closest distances are:

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

So the answer is:

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

Example 2:

s = "aaab"
c = "b"

The only "b" is at index 3.

So the answer is:

[3, 2, 1, 0]

First Thought: Check Every Occurrence

One simple approach is:

1. Store all positions where s[i] == c.
2. For every index i, compare it with every stored position.
3. Keep the minimum absolute distance.

This works, but it can be too slow.

If the string has length n, and many characters are equal to c, this can approach:

O(n^2)

We can do better by scanning the string twice.

Key Insight

For any index i, the closest occurrence of c is either:

1. The closest c on the left.
2. The closest c on the right.

So we can compute both directions separately.

First pass, left to right:

distance to closest c on the left

Second pass, right to left:

distance to closest c on the right

The answer for each index is the smaller of those two distances.

Algorithm

Let:

n = len(s)
answer = [n] * n

Use n as a large initial distance.

First pass:

1. Set prev = -n.
2. Scan from left to right.
3. Whenever s[i] == c, set prev = i.
4. Store:

answer[i] = i - prev

Second pass:

1. Set next_pos = 2 * n.
2. Scan from right to left.
3. Whenever s[i] == c, set next_pos = i.
4. Update:

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

Return answer.

Correctness

During the left-to-right pass, prev always stores the nearest occurrence of c at or before the current index. Therefore, i - prev is the distance from i to the closest c on its left side.

During the right-to-left pass, next_pos always stores the nearest occurrence of c at or after the current index. Therefore, next_pos - i is the distance from i to the closest c on its right side.

For any index, the closest occurrence of c must be either on the left or on the right. The algorithm takes the minimum of these two distances, so answer[i] becomes the shortest distance from index i to any occurrence of c.

Thus the returned array is correct.

Complexity

Let n = len(s).

Implementation

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

        prev = -n

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

            answer[i] = i - prev

        next_pos = 2 * n

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

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

        return answer

Code Explanation

We initialize the answer with a large value:

answer = [n] * n

The first pass records distance to the nearest c on the left:

prev = -n

Before any c has been seen, prev is far outside the string, so the distance is large.

Whenever we find c, we update prev:

if s[i] == c:
    prev = i

Then we store the left-side distance:

answer[i] = i - prev

The second pass records distance to the nearest c on the right:

next_pos = 2 * n

Whenever we find c, we update next_pos:

if s[i] == c:
    next_pos = i

Then we keep the smaller distance:

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

Testing

def run_tests():
    s = Solution()

    assert s.shortestToChar("loveleetcode", "e") == [
        3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0
    ]

    assert s.shortestToChar("aaab", "b") == [3, 2, 1, 0]

    assert s.shortestToChar("a", "a") == [0]

    assert s.shortestToChar("abcde", "c") == [2, 1, 0, 1, 2]

    assert s.shortestToChar("aaaaa", "a") == [0, 0, 0, 0, 0]

    print("all tests passed")

run_tests()