20. Shortest Distance to a Character

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.

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]

Solution: ( Min Array )

Taking Distance from left side Taking Distance from right side

class Solution
{
public:
    vector<int> shortestToChar(string s, char c)
    {

        int n = s.length();
        vector<int> res(n);
        int pos = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            pos = (s[i] == c) ? i : pos;
            res[i] = (pos == INT_MAX) ? INT_MAX : i - pos;
        }

        pos = INT_MAX;
        for (int i = n - 1; i >= 0; i--)
        {

            pos = (s[i] == c) ? i : pos;
            res[i] = min(res[i], (pos == INT_MAX) ? INT_MAX : pos - i);
        }

        return res;
    }
};

Time Complexity: O(n)