Check Distances Between Same Letters - Leetcode Solution

Problem:

Given a string s, return an array answer of length n, where answer[i] is the distance between the ith occurrence of letter 'c' in the string and the closest occurrence to the left of letter 'c'.

If there is no letter 'c' in the string, answer[i] should be -1.

Example 1:

Input: s = "loveleetcode"

Output: [3,2,1,0,1,0,0,1,2,2,1,-1]

Explanation: The closest occurrence of the letter 'c' for every letter in "loveleetcode" is shown below:

l o v e l e e t c o d e

     3 2 1 0 1 0 0 1 2 2 1 -1
     

Example 2:

Input: s = "aabb"

Output: [-1,-1,-1,-1]

Explanation: There is no letter 'c' in the string.

Solution:

We can use a loop to iterate over the string s and maintain a variable "prevIndex" to keep track of the last index where we found letter 'c'. We can also maintain an array "answer" to store the distance between the current occurrence of letter 'c' and the closest occurrence to the left of letter 'c'.

Algorithm:

1. Initialize "prevIndex" to -1, to indicate that we have not yet found any occurrence of letter 'c'.

2. Initialize an array "answer" of length n (where n is the number of occurrences of letter 'c' in the string) and fill it with -1, to indicate that we have not yet found any closest occurrence to the left of letter 'c'.

3. Loop over the string s and for each index i, check if s[i] is equal to letter 'c'.

4. If s[i] is equal to letter 'c', then calculate the distance d between i and prevIndex, and update answer[prevIndex] with d.

5. Then, set prevIndex to i, to keep track of the last index where we found letter 'c'.

6. After the loop, return the array answer.

Code:

Here is the code for the solution:

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.length();
        int prevIndex = -1;
        vector<int> answer;
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                if (prevIndex != -1) {
                    int d = i - prevIndex;
                    for (int j = prevIndex; j < i; j++) {
                        answer[j] = min(j - prevIndex, i - j);
                    }
                }
                prevIndex = i;
                answer.push_back(0);
            } else {
                if (prevIndex != -1) {
                    answer.push_back(i - prevIndex);
                } else {
                    answer.push_back(-1);
                }
            }
        }
        return answer;
    }
};

1