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

By Manas | 7 February 2021

February LeetCoding Challenge 2021

Day 7

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[0];
        int right = pos_of_c[1];
        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;
    }
};

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply