Problem Description

You are given a string s and a character c that appears somewhere in the string. Your task is to find the shortest distance from each position in the string to the nearest occurrence of character c.

For each index i in the string, you need to calculate the minimum distance to any position where character c appears. The distance between two indices is simply the absolute difference between them: abs(i - j).

The output should be an array of integers where:

• The array has the same length as the input string s
• Each element at index i represents the shortest distance from position i to the nearest character c

For example, if s = "loveleetcode" and c = 'e':

• The character 'e' appears at positions 3, 5, 6, and 11
• For index 0 ('l'), the nearest 'e' is at position 3, so the distance is 3
• For index 4 ('l'), the nearest 'e' is at position 3 or 5, both giving distance 1
• For index 6 ('e'), the distance is 0 since it is itself an 'e'

The solution uses a two-pass approach:

1. First pass (left to right): Track the most recent position of character c seen so far and calculate distances based on that
2. Second pass (right to left): Track the nearest future position of character c and update distances if a closer occurrence is found

This ensures that each position considers both the nearest c to its left and the nearest c to its right, giving the overall minimum distance.

Intuition

The key insight is that for any position in the string, the nearest character c can only be in one of two directions: either to the left or to the right. This means we don't need to check every possible position - we just need to know the closest c on each side.

Think of it like standing on a street looking for the nearest bus stop. You only need to check in two directions - left and right - and pick whichever is closer. You don't need to check every single point on the street.

This observation leads us to a two-pass strategy:

1. Why two passes? In a single pass from left to right, we can only know about the c characters we've already seen (those to our left). We have no information about any c characters that might be coming up ahead. Similarly, a single pass from right to left only tells us about future occurrences.

2. Tracking positions with infinity: We initialize pre = -inf for the left-to-right pass because initially, we haven't seen any c yet. Using negative infinity ensures that i - pre gives a very large distance, which is appropriate since there's no c to the left. Similarly, suf = inf for the right-to-left pass represents that initially there's no known c to the right.

3. The minimum operation: After both passes, each position has been evaluated against both its nearest left c and nearest right c. Taking the minimum ensures we get the absolute shortest distance. If a position only has c on one side, that side will naturally give the smaller distance.

4. Why this works: Every position between two c characters will get its correct distance because it considers both neighbors. Positions at the edges (before the first c or after the last c) will also get correct distances because they only have c on one side, and the infinity on the other side ensures the correct side is chosen.

The beauty of this approach is its simplicity - rather than doing complex searches for each position, we leverage the linear nature of the string to solve the problem in just two straightforward passes.

Learn more about Two Pointers patterns.

Solution Approach

Let's walk through the implementation step by step:

Initialization:

n = len(s)
ans = [n] * n
pre = -inf

• We create an answer array ans initialized with n (the length of string). This serves as an upper bound for distances since no distance can be greater than the string length.
• pre tracks the position of the most recent c encountered during the left-to-right pass, initialized to negative infinity.

First Pass (Left to Right):

for i, ch in enumerate(s):
    if ch == c:
        pre = i
    ans[i] = min(ans[i], i - pre)

• We iterate through each character from left to right.
• When we encounter the target character c, we update pre to the current position i.
• For every position, we calculate the distance to the most recent c on the left: i - pre.
• We use min(ans[i], i - pre) to keep the smaller distance. Initially, ans[i] is n, so in this first pass, we're effectively storing i - pre.
• If no c has been seen yet, i - pre will be very large (since pre = -inf), which is correct.

Second Pass (Right to Left):

suf = inf
for i in range(n - 1, -1, -1):
    if s[i] == c:
        suf = i
    ans[i] = min(ans[i], suf - i)

• We iterate through the string backwards.
• suf tracks the position of the nearest c to the right, initialized to positive infinity.
• When we encounter c, we update suf to that position.
• For each position, we calculate the distance to the nearest c on the right: suf - i.
• We update ans[i] with the minimum of its current value (distance to left c) and the distance to right c.

Why This Works:

Consider a position i in the string:

• After the first pass, ans[i] contains the distance to the nearest c on the left (or a very large value if there's no c on the left).
• After the second pass, ans[i] is updated to be the minimum of:
  • Distance to nearest c on the left (from first pass)
  • Distance to nearest c on the right (from second pass)

This guarantees that ans[i] contains the shortest distance to any c in the string.

Time and Space Complexity:

• Time: O(n) where n is the length of the string. We make exactly two passes through the string.
• Space: O(n) for the answer array (or O(1) extra space if we don't count the output array).

Example Walkthrough

Let's trace through the algorithm with s = "abaacab" and c = 'a'.

Initial Setup:

• String: "abaacab" (length = 7)
• Target character: 'a' (appears at indices 0, 2, 3, 5)
• Initialize ans = [7, 7, 7, 7, 7, 7, 7]
• Set pre = -inf

First Pass (Left to Right):

After first pass: ans = [0, 1, 0, 0, 1, 0, 1]

Second Pass (Right to Left):

Final Result: [0, 1, 0, 0, 1, 0, 1]

Verification:

• Index 0 ('a'): Distance is 0 (it is 'a' itself) ✓
• Index 1 ('b'): Nearest 'a' is at index 0 or 2, both at distance 1 ✓
• Index 2 ('a'): Distance is 0 (it is 'a' itself) ✓
• Index 3 ('a'): Distance is 0 (it is 'a' itself) ✓
• Index 4 ('c'): Nearest 'a' is at index 3 or 5, both at distance 1 ✓
• Index 5 ('a'): Distance is 0 (it is 'a' itself) ✓
• Index 6 ('b'): Nearest 'a' is at index 5, distance is 1 ✓

The algorithm correctly finds the shortest distance to 'a' for each position by considering both directions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of string s. The algorithm makes two passes through the string:

• First pass: iterates from left to right through all n characters, performing constant time operations (comparison, assignment, and minimum calculation) for each character
• Second pass: iterates from right to left through all n characters, again performing constant time operations for each character
• Total: O(n) + O(n) = O(2n) = O(n)

Space Complexity: O(n), where n is the length of string s. The algorithm uses:

• ans array: stores n integers to hold the result, requiring O(n) space
• Other variables (n, pre, suf, i, ch): constant space O(1)
• Total: O(n) + O(1) = O(n)

Note: The space complexity analysis excludes the output array from consideration as it's required for the problem's result. If we include the output array, the space complexity remains O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization of Boundary Values

Pitfall: Using incorrect initial values for pre and suf variables, such as:

• Setting pre = 0 or suf = n-1 instead of infinity values
• Using pre = None or suf = None without proper handling

Why it's wrong: If you initialize pre = 0, then for characters before the first occurrence of c, the distance calculation i - pre would give incorrect small values instead of representing "no character c found yet."

Incorrect Example:

pre = 0  # Wrong!
for i, ch in enumerate(s):
    if ch == c:
        pre = i
    ans[i] = i - pre  # This gives wrong distance when no 'c' found yet

Solution: Always use float('-inf') for pre and float('inf') for suf to ensure that positions without a nearby c get properly large distance values that will be overwritten by the correct minimum.

2. Forgetting to Use min() When Updating Distances

Pitfall: Directly assigning distances without comparing with existing values:

# Wrong approach - overwrites instead of keeping minimum
for i in range(n - 1, -1, -1):
    if s[i] == c:
        suf = i
    ans[i] = suf - i  # Should be min(ans[i], suf - i)

Why it's wrong: The second pass would completely overwrite the distances calculated in the first pass, losing information about closer occurrences of c on the left side.

Solution: Always use min(ans[i], new_distance) to ensure you're keeping the shortest distance from either direction.

3. Off-by-One Errors in Range Iteration

Pitfall: Using incorrect range boundaries in the backward pass:

# Wrong - misses the first element
for i in range(n - 1, 0, -1):  # Should be range(n - 1, -1, -1)
    ...

Why it's wrong: This would skip index 0, leaving its distance potentially incorrect if there's a c to its right but not to its left.

Solution: Use range(n - 1, -1, -1) to ensure all indices from n-1 down to 0 are processed.

4. Not Handling Edge Cases with Single Character

Pitfall: Assuming the string has multiple characters without checking:

# Might fail for s = "e", c = "e"
if n == 1:
    return [0] if s[0] == c else [1]  # Wrong logic

Why it's wrong: Single character strings are valid inputs and the algorithm should handle them naturally without special cases.

Solution: The two-pass algorithm handles single character strings correctly without special casing. When s = "e" and c = "e", both passes will correctly set the distance to 0.