##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/821.html

# 821. Shortest Distance to a Character (Easy)

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]


Note:

1. S string length is in [1, 10000].
2. C is a single character, and guaranteed to be in string S.
3. All letters in S and C are lowercase.

Companies:
Bloomberg

## Solution 1.

// OJ: https://leetcode.com/problems/shortest-distance-to-a-character/
// Time: O(N)
// Space: O(1)
class Solution {
public:
vector<int> shortestToChar(string S, char C) {
int N = S.size(), prevJ;
vector<int> ans(N);
for (int i = 0, j = -1; i < N; ++i) {
if (i > j) {
prevJ = j;
do { ++j; } while (j < N && S[j] != C);
}
ans[i] = min(j == N ? INT_MAX : j - i, prevJ == -1 ? INT_MAX : i - prevJ);
}
return ans;
}
};

• class Solution {
public int[] shortestToChar(String S, char C) {
int length = S.length();
int[] distances = new int[length];
List<Integer> indices = new ArrayList<Integer>();
for (int i = 0; i < length; i++) {
if (S.charAt(i) == C)
}
int size = indices.size();
int pointer = 0;
for (int i = 0; i < length; i++) {
if (indices.contains(i)) {
distances[i] = 0;
pointer++;
} else {
if (pointer == 0) {
int curIndex = indices.get(pointer);
distances[i] = Math.abs(curIndex - i);
} else if (pointer == size) {
int prevIndex = indices.get(pointer - 1);
distances[i] = Math.abs(i - prevIndex);
} else {
int prevIndex = indices.get(pointer - 1), curIndex = indices.get(pointer);
distances[i] = Math.min(Math.abs(i - prevIndex), Math.abs(curIndex - i));
}
}
}
return distances;
}
}

############

class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] ans = new int[n];
for (int i = 0, j = Integer.MAX_VALUE; i < n; ++i) {
if (s.charAt(i) == c) {
j = i;
}
ans[i] = Math.abs(i - j);
}
for (int i = n - 1, j = Integer.MAX_VALUE; i >= 0; --i) {
if (s.charAt(i) == c) {
j = i;
}
ans[i] = Math.min(ans[i], Math.abs(i - j));
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/shortest-distance-to-a-character/
// Time: O(N)
// Space: O(1)
class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int N = s.size(), prev = -N, next = 0;
vector<int> ans(N);
for (int i = 0; i < N; ++i) {
while (next < N && s[next] != c) ++next;
if (next == N) next = N + N;
ans[i] = min(i - prev, next - i);
if (s[i] == c) prev = i, next++;
}
return ans;
}
};

• class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
n = len(s)
ans = [0] * n
j = inf
for i, ch in enumerate(s):
if ch == c:
j = i
ans[i] = abs(i - j)
j = inf
for i in range(n - 1, -1, -1):
if s[i] == c:
j = i
ans[i] = min(ans[i], abs(i - j))
return ans

############

class Solution:
def shortestToChar(self, S, C):
"""
:type S: str
:type C: str
:rtype: List[int]
"""
_len = len(S)
index = -1000000
ans = [0] * _len
for i, s in enumerate(S):
if s == C:
index = i
ans[i] = abs(i - index)
index = -100000
for i in range(_len - 1, -1 , -1):
if S[i] == C:
index = i
ans[i] = min(abs(i - index), ans[i])
return ans

• func shortestToChar(s string, c byte) []int {
n := len(s)
ans := make([]int, n)
for i, j := 0, -10000; i < n; i++ {
if s[i] == c {
j = i
}
ans[i] = i - j
}
for i, j := n-1, 10000; i >= 0; i-- {
if s[i] == c {
j = i
}
if j-i < ans[i] {
ans[i] = j - i
}
}
return ans
}

• function shortestToChar(s: string, c: string): number[] {
const n = s.length;
let ans = [];
let pre = Infinity;
for (let i = 0; i < n; i++) {
if (s.charAt(i) == c) pre = i;
ans[i] = Math.abs(pre - i);
}
pre = Infinity;
for (let i = n - 1; i > -1; i--) {
if (s.charAt(i) == c) pre = i;
ans[i] = Math.min(Math.abs(pre - i), ans[i]);
}
return ans;
}


• impl Solution {
pub fn shortest_to_char(s: String, c: char) -> Vec<i32> {
let c = c as u8;
let s = s.as_bytes();
let n = s.len();
let mut res = vec![i32::MAX; n];
let mut pre = i32::MAX;
for i in 0..n {
if s[i] == c {
pre = i as i32;
}
res[i] = i32::abs(i as i32 - pre);
}
pre = i32::MAX;
for i in (0..n).rev() {
if s[i] == c {
pre = i as i32;
}
res[i] = res[i].min(i32::abs(i as i32 - pre));
}
res
}
}