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.
1#include <vector>
2#include <string>
3#include <algorithm>
4using namespace std;
5
6vector<int> shortestToChar(string s, char c) {
7 int n = s.size();
8 vector<int> result(n, n);
9 int prev = -n;
10
11 // Left to right
12 for (int i = 0; i < n; ++i) {
13 if (s[i] == c) prev = i;
14 result[i] = i - prev;
}
// Right to left
for (int i = n - 1, prev = 2 * n; i >= 0; --i) {
if (s[i] == c) prev = i;
result[i] = min(result[i], prev - i);
}
return result;
}The C++ solution makes use of a vector to store the result, initialized with the maximum possible distances. In the first pass from left to right, whenever a c is found, prev is updated. The distance is calculated and stored in the result vector. In the second pass, from right to left, the vector is updated with the minimum distance calculated using the last found position of c.