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.
1import java.util.*;
2
3class Solution {
4 public int[] shortestToChar(String s, char c) {
5
The Java solution works similarly to the C++ approach. Two passes across the string are performed. After the left-to-right pass, the minimum distance from each position to its left nearest c is calculated. The right-to-left pass adjusts these distances using the minimum between the existing value and the recently calculated right side distance.