Sponsored
Sponsored
This approach involves two passe through the string:
c. Calculate the distance from the current index to this recent c.c found on this traversal.This ensures each element in the result is the minimum distance to any occurrence of c.
Time Complexity: O(n), where n is the length of the string since we go through the string twice.
Space Complexity: O(1) additional space for variables, aside from the output array.
1def shortestToChar(s: str, c: str) -> list:
2 n = len(s)
3 result = [0] * n
4
The Python solution initializes a result list of same length as s to store shortest distances. It computes distances moving from left to right, and corrects them while moving from right to left using the minimum distance found from a c on the right.