Solution: Shortest Distance to a Character
Tags: algorithms, javascript, java, leetcode
Published: 2021-02-07 09:17:52

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/shortest-distance-to-a-character/discuss/1054148/Javascript-or-Simple-DP-Solution-w-Explanation-or-beats-99-100).*

---

####[Leetcode Problem #821 (*Easy*): Shortest Distance to a Character](https://leetcode.com/problems/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%).
```javascript
var shortestToChar = function(S, C) {
    let len = S.length, ans = new Uint16Array(len)
    ans[0] = 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%).
```python
class Solution:
    def shortestToChar(self, S: str, C: str) -> List[int]:
        ans = []
        ans.append(0 if S[0] == 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%).
```java
class Solution {
    public int[] shortestToChar(String S, char C) {
        int len = S.length();
        int[] ans = new int[len];
        ans[0] = 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%).
```c++
class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int len = S.length();
        std::vector<int> ans;
        ans.push_back(S[0] == 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;
    }
};
```