Shortest Distance to a Character | February challenge 2021 | Day 7 Manas Sinha
Developer | Designer

SHORTEST DISTANCE TO A CHARACTER

PROBLEM  STATEMENT:
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]
Constraints:
• 1 <= s.length <= 104
• s[i] and c are lowercase English letters.
• c occurs at least once in s.

Explanation

This problem can be solved using two pointer method.
ALGORITHM:
• Store position of all the occurrences of c in an seperate array
• Every character in s will have one c in left and another in right. If not assume it to be at infinity.
• Traverse the string.
• The left and right pointer tracks the two positions of c in between of which lies the the current character.
• Find the minimum of the two distances, i.e., from right and left.
• Add it to the result array. code

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

for(int i=0;i<s.length();++i){
if(s[i] == c) pos_of_c.push_back(i);
}
pos_of_c.push_back(INT_MAX);
int left = pos_of_c;
int right = pos_of_c;
int next_pos = 2;
vector<int> res;
for(int i=0;i<s.length();++i){
if(i>right){
left = right;
right = pos_of_c[next_pos];
next_pos++;
}

res.push_back(min(abs(i-left),abs(right-i)));

}
return res;
}
};