## DEV Community is a community of 604,099 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # Solution: Shortest Distance to a Character

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Leetcode Problem #821 (Easy): Shortest Distance to a Character

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 shortest distance from `s[i]` to the character `c` in `s`.

Examples:

Example 1:
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Example 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.
• `c` occurs at least once in `s`.

Idea:

Since this problem is asking us to reference characters both ahead and behind the current charcter, this should bring to mind a two-pass dynamic programming solution. We can iterate through the input string (S) once and fill our answer array (ans) with the distance from the preceeding occurrence of C.

Then we can iterate backwards through S again so that we can pick the best result between the value we obtained in the first pass with the distance from the preceeding C going the opposite direction.

Javascript Code:

The best result for the code below is 80ms / 39.0MB (beats 99% /100%).

``````var shortestToChar = function(S, C) {
let len = S.length, ans = new Uint16Array(len)
ans = S.charAt(0) === C ? 0 : 10001
for (let i = 1; i < len; i++)
ans[i] = S.charAt(i) === C ? 0 : ans[i-1] + 1
for (let i = len - 2; ~i; i--)
ans[i] = Math.min(ans[i], ans[i+1] + 1)
return ans
};
``````

Python3 Code:

The best result for the code below is 28ms / 14.3MB (beats 99% / 86%).

``````class Solution:
def shortestToChar(self, S: str, C: str) -> List[int]:
ans = []
ans.append(0 if S == C else 10001)
for i in range(1,len(S)):
ans.append(0 if S[i] == C else ans[i-1] + 1)
for i in range(len(S)-2,-1,-1):
ans[i] = min(ans[i], ans[i+1] + 1)
return ans
``````

Java Code:

The best result for the code below is 1ms / 38.8MB (beats 97% / 93%).

``````class Solution {
public int[] shortestToChar(String S, char C) {
int len = S.length();
int[] ans = new int[len];
ans = S.charAt(0) == C ? 0 : 10001;
for (int i = 1; i < len; i++)
ans[i] = S.charAt(i) == C ? 0 : ans[i-1] + 1;
for (int i = len - 2; i >= 0; i--)
ans[i] = Math.min(ans[i], ans[i+1] + 1);
return ans;
}
}
``````

C++ Code:

The best result for the code below is 0ms /6.5MB (beats 100% / 97%).

``````class Solution {
public:
vector<int> shortestToChar(string S, char C) {
int len = S.length();
std::vector<int> ans;
ans.push_back(S == C ? 0 : 10001);
for (int i = 1; i < len; i++)
ans.push_back(S[i] == C ? 0 : ans[i-1] + 1);
for (int i = len - 2; i >= 0; i--)
ans[i] = min(ans[i], ans[i+1] + 1);
return ans;
}
};
``````

## Discussion (0) 