algoadvance

Leetcode 821. Shortest Distance to a Character

Problem Statement

Given a string s and a character c that occurs in s, return an array of integers representing the shortest distance from the character c in the string.

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]

Clarifying Questions

  1. Are there any constraints on the length of the string s?
    • The length of s will be in the range [1, 10^4].
  2. Are all characters in the string s lowercase English letters?
    • Yes, all characters in s are lowercase English letters.
  3. Does the character c always appear in the string s?
    • Yes, the character c always appears at least once in the string s.
  4. What should be returned if s contains only the character c?
    • Return an array of zeros with the same length as s, since the distance to c is zero at every position.

Strategy

To solve the problem efficiently, we will:

  1. Initialize an array result of the same length as s with large values (like infinity).
  2. Do a forward pass to fill out the shortest distances to c considering only the previous occurrences of c.
  3. Do a backward pass to refine the distances using the next occurrences of c.

Steps:

  1. Iterate through the string from left to right:
    • Update the current distance when encountering the character c.
    • Update the result array with this distance for each position.
  2. Iterate through the string from right to left:
    • Similarly, update the current distance when encountering the character c.
    • Update the result array to ensure the shortest distance is recorded for each position.

Time Complexity

Code

#include <vector>
#include <string>
#include <algorithm>
#include <climits>

std::vector<int> shortestToChar(const std::string &s, char c) {
    int n = s.size();
    std::vector<int> result(n, INT_MAX);
    
    // Forward pass
    int prev = -INT_MAX;
    for (int i = 0; i < n; ++i) {
        if (s[i] == c) {
            prev = i;
        }
        result[i] = std::min(result[i], abs(i - prev));
    }
    
    // Backward pass
    prev = INT_MAX;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == c) {
            prev = i;
        }
        result[i] = std::min(result[i], abs(i - prev));
    }
    
    return result;
}

By structuring the solution in two passes, we ensure the correct shortest distance is captured for each position in the string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI