Shortest Distance To A Character Problem


Description

LeetCode Problem 821.

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:

1
2
3
4
5
6
7
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:

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

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> res;
        int prev_char = -s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == c)
                prev_char = i;
            res.push_back(i - prev_char);
        }

        for (int i = prev_char; i >= 0; i--) {
            if (s[i] == c)
                prev_char = i;
            res[i] = min(res[i], prev_char - i);
        }
        return res;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...