Algorithm
Problem Name: 821. 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.
Example 2:
Input: s = "aaab", c = "b" Output: [3,2,1,0]
Constraints:
1 <= s.length <= 104s[i]andcare lowercase English letters.- It is guaranteed that
coccurs at least once ins.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> shortestToChar(string S, char C) {
vector<int>pos, res;
for(int i = 0; i < S.size(); i++) if(S[i] == C) pos.push_back(i);
for(int i = 0, p = 0; i < S.size(); i++){
if(p < pos.size() && i == pos[p]) p++;
res.push_back(p == 0 ? pos[0] - i : p == pos.size() ? i - pos[p - 1] : min(i - pos[p - 1], pos[p] - i)>;
}
return res;
}
};
Input
s = "loveleetcode", c = "e"
Output
[3,2,1,0,1,0,0,1,2,2,1,0]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] shortestToChar(String S, char C) {
int[] ans = new int[S.length()];
int prev = Integer.MIN_VALUE / 2;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == C) {
prev = i;
}
ans[i] = i - prev;
}
prev = Integer.MAX_VALUE / 2;
for (int i = S.length() - 1; i >= 0; i--) {
if (S.charAt(i) == C) {
prev = i;
}
ans[i] = Math.min(ans[i], prev - i);
}
return ans;
}
}
Input
s = "loveleetcode", c = "e"
Output
[3,2,1,0,1,0,0,1,2,2,1,0]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const shortestToChar = function(S, C) {
const res = [];
const idxArr = [];
for (let i = 0; i < S.length; i++) {
S.charAt(i) === C ? idxArr.push(i) : null;
}
let coordIdx = 0;
let nextCoordIdx = 1;
let val;
for (let idx = 0; idx < S.length; idx++) {
if (S.charAt(idx) === C) {
val = 0;
nextCoordIdx = idxArr[coordIdx + 1] == null ? coordIdx : coordIdx + 1;
if (
Math.abs(idxArr[coordIdx] - idx) >= Math.abs(idxArr[nextCoordIdx] - idx)
) {
coordIdx = idxArr[coordIdx + 1] == null ? coordIdx : coordIdx + 1;
}
} else {
nextCoordIdx = idxArr[coordIdx + 1] == null ? coordIdx : coordIdx + 1;
if (
Math.abs(idxArr[coordIdx] - idx) < Math.abs(idxArr[nextCoordIdx] - idx)
) {
val = Math.abs(idxArr[coordIdx] - idx);
} else {
val = Math.abs(idxArr[nextCoordIdx] - idx);
coordIdx = idxArr[coordIdx + 1] == null ? coordIdx : coordIdx + 1;
}
}
res[idx] = val;
}
return res;
};
console.log(shortestToChar("aaab", "b"));
console.log(shortestToChar("bbba", "b"));
Input
s = "aaab", c = "b"
Output
[3,2,1,0]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def shortestToChar(self, S, C):
"""
:type S: str
:type C: str
:rtype: List[int]
"""
char1, char2, diff1, diff2, res = False, False, 0, 0, [None]* len(S)
for i in range(len(S)):
if char1: res[i], diff1 = min(res[i], diff1 + 1) if res[i] else diff1 + 1, diff1 + 1
if S[i] == C: diff1, res[i], char1 = 0, 0, True
if char2: res[len(S) - 1 - i], diff2 = min(res[len(S) - 1 - i], diff2 + 1) if res[len(S) - 1 - i] else diff2 + 1, diff2 + 1
if S[len(S) - 1 - i] == C: diff2, res[len(S) - 1 - i], char2 = 0, 0, True
return res
Input
s = "aaab", c = "b"
Output
[3,2,1,0]
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0821_ShortestDistanceToACharacter
{
public int[] ShortestToChar(string S, char C)
{
var result = new int[S.Length];
var distance = S.Length;
for (int i = 0; i < S.Length; i++)
{
if (S[i] == C)
{
result[i] = 0;
distance = 1;
}
else
{
if (result[i] < distance)
result[i] = distance++;
}
}
distance = S.Length;
for (int i = S.Length - 1; i >= 0; i--)
{
if (S[i] == C)
distance = 1;
else
{
if (result[i] > distance)
result[i] = distance++;
}
}
return result;
}
}
}
Input
s = "aaab", c = "b"
Output
[3,2,1,0]