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.
1using System;
2
3public class Solution {
4 public int[] ShortestToChar(string s, char c) {
5 int n = s.Length;
6 int[] result = new int[n];
7 int prev = -n;
8
9 // Forward pass
10 for (int i = 0; i < n; i++) {
11 if (s[i] == c) prev = i;
12 result[i] = i - prev;
13 }
14
// Backward pass
for (int i = n - 1; i >= 0; i--) {
if (s[i] == c) prev = i;
result[i] = Math.Min(result[i], Math.Abs(i - prev));
}
return result;
}
}The C# implementation involves computing distances in a fashion similar to previous languages, first by updating with distances to the nearest left instance of c, and then adjusting with distances to the nearest right instance of c in a backwards pass.