Shortest Distance To A Character - Leetcode Solution

Problem Statement:

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 shortest distance from s[i] to the character c in s.

Solution:

The solution to this problem can be done using a two-pointer approach. Let's consider two pointers left and right.

Initialize the left pointer to -1 and right pointer to the first occurrence of the character c in the string s. Initialize the answer array with all zeroes.

Now, we start iterating through the string s from the left to right. For each index i, we calculate the distance between i and the left and right pointers.

The answer for index i will be the minimum of the distance from i to the left and the distance from i to the right.

If the character s[i] is equal to c, we update the left pointer to i and reset the right pointer to the next occurrence of the character c in the string s.

Pseudo Code:

left = -1 right = s.index(c)

for i in range(len(s)): if s[i] == c: left = i right = s.index(c, i+1) if c in s[i+1:] else -1 if left == -1: answer[i] = right - i elif right == -1: answer[i] = i - left else: answer[i] = min(i - left, right - i)

Now, let's discuss the time complexity of this algorithm. We only iterate through the string s once, so the time complexity of this algorithm is O(n).

Python Code:

def shortestToChar(s: str, c: str) -> List[int]: left = -1 right = s.index(c) answer = [0] * len(s)

for i in range(len(s)):
    if s[i] == c:
        left = i
        right = s.index(c, i+1) if c in s[i+1:] else -1
    
    if left == -1:
        answer[i] = right - i
    elif right == -1:
        answer[i] = i - left
    else:
        answer[i] = min(i - left, right - i)

return answer

This solution passed all the test cases on LeetCode.

1