Shortest Distance to a Character

EASY

Description

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.

The distance between two indices i and j is abs(i - j), where abs is the absolute value function.

Example 1:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

Example 2:

Input: s = "aaab", c = "b"
Output: [3,2,1,0]

Constraints:

1 <= s.length <= 10⁴
s[i] and c are lowercase English letters.
It is guaranteed that c occurs at least once in s.

Approaches

Checkout 3 different approaches to solve Shortest Distance to a Character. Click on different approaches to view the approach and algorithm in detail.

Brute Force

The most straightforward approach is to iterate through each character of the string. For each character, we perform another full scan of the string to find the closest occurrence of the target character c.

Algorithm

Initialize an integer array answer with the same length as s.
Loop through each index i from 0 to s.length() - 1.
Inside the loop, initialize minDistance to Integer.MAX_VALUE.
Start a nested loop for each index j from 0 to s.length() - 1.
If s.charAt(j) is equal to c, update minDistance with Math.min(minDistance, Math.abs(i - j)).
After the inner loop, set answer[i] = minDistance.
Return the answer array.

For every index i in the string s, we initialize a minimum distance to a very large value. Then, we iterate through the entire string again with an index j. If the character at index j is the target character c, we calculate the distance abs(i - j) and update our minimum distance if this new distance is smaller. After checking all j's for a given i, the resulting minimum distance is stored in our answer array at index i.

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int minDistance = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == c) {
                    minDistance = Math.min(minDistance, Math.abs(i - j));
                }
            }
            answer[i] = minDistance;
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the string `s`. For each of the N characters, we iterate through the entire string again, leading to a quadratic time complexity.Space Complexity: O(N) for the output array `answer`. If the output array is not considered, the space complexity is O(1).

Pros and Cons

Pros:

Very simple to conceptualize and implement.

Cons:

Highly inefficient and will likely result in a 'Time Limit Exceeded' error for larger inputs as specified in the constraints.

Code Solutions

Checking out 3 solutions in different languages for Shortest Distance to a Character. Click on different languages to view the code.

class Solution {
public
  int[] shortestToChar(String s, char c) {
    int n = s.length();
    int[] ans = new int[n];
    final int inf = 1 << 30;
    Arrays.fill(ans, inf);
    for (int i = 0, pre = -inf; i < n; ++i) {
      if (s.charAt(i) == c) {
        pre = i;
      }
      ans[i] = Math.min(ans[i], i - pre);
    }
    for (int i = n - 1, suf = inf; i >= 0; --i) {
      if (s.charAt(i) == c) {
        suf = i;
      }
      ans[i] = Math.min(ans[i], suf - i);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Shortest Distance to a Character

Patterns:

Two Pointers

Data Structures:

ArrayString