DEV Community

Cover image for Solution: Shortest Distance to a Character
seanpgallivan
seanpgallivan

Posted on

3 1

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
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Please leave your appreciation by commenting on this post!

Okay, let's go.

Happy coding ❤️

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

đź‘‹ Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay