{x}
blog image

Shortest Distance to a Character

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.

The distance between two indices i and j is abs(i - j), where abs is the absolute value function.

 

Example 1:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: 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]

 

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 Explanation

This problem asks to find the shortest distance from each character in a string s to the nearest occurrence of a specific character c. The solution uses a two-pointer approach with a single pass through the array to achieve linear time complexity.

Algorithm:

  1. Initialization: Create an array ans of the same length as the input string s, initially filled with a large value (representing infinity) to store the minimum distances.

  2. Forward Pass: Iterate through the string from left to right. Maintain a variable pre to track the index of the most recently encountered character c. For each index i:

    • If s[i] == c, update pre to i.
    • Calculate the distance i - pre and update ans[i] to the minimum of its current value and this distance. This ensures we store the shortest distance from the character to c up to this point.

  3. Backward Pass: Iterate through the string from right to left. Maintain a variable suf to track the index of the most recently encountered character c from the right. For each index i:

    • If s[i] == c, update suf to i.
    • Calculate the distance suf - i and update ans[i] to the minimum of its current value and this distance. This handles cases where the closest c is to the right of the current index.

  4. Return: Return the ans array containing the shortest distances for each index.

Time Complexity: O(N), where N is the length of the string, due to the two single passes through the string.

Space Complexity: O(N) to store the ans array.

Code Explanation (Python):

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [n] * n  # Initialize with a large value (n)
        pre = -inf     # Initialize pre to negative infinity
        for i, ch in enumerate(s):
            if ch == c:
                pre = i
            ans[i] = min(ans[i], i - pre) # Update ans with the minimum distance from left
 
        suf = inf      # Initialize suf to positive infinity
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                suf = i
            ans[i] = min(ans[i], suf - i) # Update ans with minimum distance from right
        return ans

The other language examples follow the same logic, adapting the syntax and data structures specific to each language. The core idea of the two-pass approach remains consistent across all implementations.