Leetcode 841 Solution

This article provides solution to leetcode question 841 (shortest-distance-to-a-character)

https://leetcode.com/problems/shortest-distance-to-a-character

Solution

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        queue<int> q;
        vector<int> a(S.size(), INT_MAX);

        int last_pos = -1;
        for (int i = 0; i < S.size(); i++)
        {
            if (S[i] == C)
                last_pos = i;

            if (last_pos == -1)
                continue;

            a[i] = min(a[i], i - last_pos);
        }

        last_pos = -1;
        for (int i = S.size() - 1; i >= 0; i--)
        {
            if (S[i] == C)
                last_pos = i;

            if (last_pos == -1)
                continue;

            a[i] = min(a[i], last_pos - i);
        }

        return a;
    }
};