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[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%).

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%).

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%).

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;
    }
};