Shortest Distance to a Character

Problem

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 distance from index i to the closest occurrence of character c in s.

The distance between two indices i and j is abs(i - j), where abs is the absolute value function.

Constraints

• 1 <= s.length <= 104
• s[i] and c are lowercase English letters.
• It is guaranteed that c occurs at least once in s.

Solution

The problem Shortest Distance to a Character can be solved by calculating the distance twice from c that is on its left and from c that is on the right. THe closest occurence of character c to an integer on index i can be gained from the minimum value between two distances.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    vector<int> shortestToChar(string s, char c)
    {
        vector<int> ret(s.length(), INT_MAX);

        int left = 0, right = s.length() - 1;
        while (s[left] != c)
            left += 1;
        while (s[right] != c)
            right -= 1;

        for (int i = left; i < s.length(); i++)
            ret[i] = s[i] == c ? 0 : ret[i - 1] + 1;
        for (int i = right - 1; i >= 0; i--)
            ret[i] = min(ret[i], ret[i + 1] + 1);

        return ret;
    }
};