821. Shortest Distance to a Character LeetCode Solution

In this guide, you will get 821. Shortest Distance to a Character LeetCode Solution with the best time and space complexity. The solution to Shortest Distance to a Character problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Shortest Distance to a Character solution in C++
  4. Shortest Distance to a Character solution in Java
  5. Shortest Distance to a Character solution in Python
  6. Additional Resources
821. Shortest Distance to a Character LeetCode Solution image

Problem Statement of Shortest Distance to a Character

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.

See also  1240. Tiling a Rectangle with the Fewest Squares LeetCode Solution

Example 2:

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

Constraints:

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

821. Shortest Distance to a Character LeetCode Solution in C++

class Solution {
 public:
  vector<int> shortestToChar(string s, char c) {
    const int n = s.length();
    vector<int> ans(n);
    int prev = -n;

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

    for (int i = prev - 1; i >= 0; --i) {
      if (s[i] == c)
        prev = i;
      ans[i] = min(ans[i], prev - i);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

821. Shortest Distance to a Character LeetCode Solution in Java

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

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

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

    return ans;
  }
}
// code provided by PROGIEZ

821. Shortest Distance to a Character LeetCode Solution in Python

class Solution:
  def shortestToChar(self, s: str, c: str) -> list[int]:
    n = len(s)
    ans = [0] * n
    prev = -n

    for i in range(n):
      if s[i] == c:
        prev = i
      ans[i] = i - prev

    for i in range(prev - 1, -1, -1):
      if s[i] == c:
        prev = i
      ans[i] = min(ans[i], prev - i)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: