LeetCode 821: Shortest Distance to a Character

Explanation

To solve this problem, we can iterate through the string s twice. In the first iteration, we find the distance to the closest occurrence of character c by going from left to right. In the second iteration, we find the distance from the closest occurrence of character c by going from right to left. We then take the minimum of these two distances at each index to get the final answer array.

• Algorithm:

  1. Initialize two arrays left and right of size s.length() to store the distances from left and right respectively.
  2. Initialize variables prev and result to store the previous occurrence index of character c and the final answer array.
  3. Iterate through the string s from left to right, updating left and prev.
  4. Iterate through the string s from right to left, updating right and calculating the minimum distance.

• Time Complexity: O(N) where N is the length of the input string s.

• Space Complexity: O(N) for the two arrays left and right.

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        int prev = Integer.MIN_VALUE / 2;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                prev = i;
            }
            ans[i] = i - prev;
        }

        prev = Integer.MAX_VALUE / 2;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                prev = i;
            }
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }
}