#821

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Shortest Distance to a Character

Compute the minimum distance from each character in a string to a target character using efficient scanning techniques.

Problem Statement

Given a string s and a character c that is guaranteed to appear in s, return an array answer where answer[i] represents the shortest distance from index i to any occurrence of character c. The distance between indices i and j is defined as abs(i - j).

For example, if s = "loveleetcode" and c = 'e', the answer array should reflect the minimal distance from each index to the nearest 'e', producing [3,2,1,0,1,0,0,1,2,2,1,0]. Constraints include 1 <= s.length <= 10^4 and all characters being lowercase English letters.

Examples

Example 1

Input: s = "loveleetcode", c = "e"

Output: [3,2,1,0,1,0,0,1,2,2,1,0]

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]

Example details omitted.

Constraints

1 <= s.length <= 104
s[i] and c are lowercase English letters.
It is guaranteed that c occurs at least once in s.

Solution Approach

Two-pass left-to-right and right-to-left scan

Initialize an answer array with large values. Scan the string from left to right, updating distances to the last seen target character. Then scan from right to left to correct distances considering targets on the right, ensuring each answer[i] holds the minimum distance.

Maintain the nearest target index invariant

Track the index of the most recent occurrence of character c while scanning. This invariant ensures that at any position, you can compute the distance to the nearest left or right occurrence efficiently without additional searches.

Edge handling and absolute value calculation

Handle positions before the first and after the last occurrence of c carefully, initializing with extreme values. Use abs(i - lastSeen) to compute distances correctly, guaranteeing correctness across the full string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is visited twice (left-to-right and right-to-left). Space complexity is O(n) for the output array; additional space is O(1) for tracking indices. This pattern avoids nested loops and redundant distance computations.

What Interviewers Usually Probe

Notice if the candidate attempts nested loops instead of two-pass scanning.
Check if they correctly handle indices before the first and after the last occurrence of c.
Observe whether they maintain an invariant for the nearest target character index.

Common Pitfalls or Variants

Common pitfalls

Using a brute-force approach that computes distances to all occurrences for each index, causing O(n^2) time.
Failing to update distances correctly in the second (right-to-left) pass, leading to incorrect minimal distances.
Not handling edge indices properly when the target character has not yet appeared in the scan.

Follow-up variants

Compute shortest distances to multiple target characters simultaneously, extending the invariant tracking.
Return the indices of the closest occurrence instead of distances, requiring minor modification to the scan.
Handle a dynamic string where characters can be added or removed, updating distances incrementally.

FAQ

What is the best approach for Shortest Distance to a Character?

Two-pointer scanning with invariant tracking is optimal, performing left-to-right and right-to-left passes to ensure minimal distances.

How do I handle indices before the first or after the last occurrence of the target character?

Initialize distances with large values and update only when a target character has been seen in the scan, correcting in the opposite direction pass.

Can this problem be solved in O(n) time?

Yes, using the two-pass scan ensures each character is visited twice, giving O(n) time complexity.

Does the approach handle ties automatically?

Yes, since we take the minimum distance from left and right passes, ties are resolved correctly without extra comparisons.

Is extra space needed besides the output array?

No significant extra space is needed; only variables to track the last seen target index are required.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [n] * n
        pre = -inf
        for i, ch in enumerate(s):
            if ch == c:
                pre = i
            ans[i] = min(ans[i], i - pre)
        suf = inf
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                suf = i
            ans[i] = min(ans[i], suf - i)
        return ans

Continue Practicing

#809 expressive words #942 di string match #1023 camelcase matching