Shortest Distance to a Character

Problem Description

So, you’re walking down the street, minding your own business, when suddenly you realize you’ve lost your favorite character (let’s call it ‘c’). Now, you’re on a mission to find out how far you are from the nearest ‘c’ in a string. Sounds like a fun scavenger hunt, right? Well, that’s exactly what the “Shortest Distance to a Character” problem is all about!

In this LeetCode challenge, you’re given a string s and a character c. Your task is to return an array where each element at index i is the shortest distance from the character c in the string. It’s like trying to find the nearest coffee shop in a new city—except instead of coffee, it’s a character, and instead of a city, it’s a string.

Code Solution


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

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

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

        return ans

Approach Explanation

The provided code uses a two-pass approach to solve the problem efficiently. In the first pass, it calculates the distance from the last seen occurrence of the character c for each index in the string. In the second pass, it does the same but in reverse, ensuring that the minimum distance is recorded for each index. This way, you get the shortest distance to the character c without having to search through the string multiple times.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

Real-World Example

Imagine you’re at a concert, and you’re trying to find your friend who’s wearing a bright red shirt (let’s say ‘c’). You start from your spot and look around. The first time you see your friend, you note the distance. But then, as you keep looking, you realize you can see your friend again from a different angle, and you measure that distance too. You want to know the shortest distance to your friend at any point in time. This is exactly what the algorithm does—it keeps track of the shortest distance to the character c as it scans through the string.