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 s.

Clarifying Questions

  1. Can characters in s be uppercase or lowercase?
    • Typically yes, string s can have any characters including uppercase and lowercase letters.
  2. Can the character c be an uppercase or lowercase letter?
    • Yes, c can be any character including uppercase and lowercase letters.
  3. What kind of constraints should we consider (e.g., length of s)?
    • Usually, constraints are mentioned in the problem statement. Let’s assume the string length can be up to 10^4 for this explanation.
  4. Are there any edge cases we should consider?
    • Yes, cases where s is very short, where c is the first or the last character, or where c appears consecutively in s.

Strategy

  1. Initialize an array to store the shortest distances. Set it to a large value (like Integer.MAX_VALUE) initially.
  2. First pass (left to right): Keep track of the most recent position of c and update the shortest distance using this position.
  3. Second pass (right to left): Similarly, keep track of the most recent position of c and update the shortest distances from this run through.
  4. This ensures that every element in the array is the minimum distance to the nearest c.

Code

public class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] result = new int[n];
        
        // Initialize all distances to a large number
        int inf = Integer.MAX_VALUE;
        
        // Left to right pass
        int position = -inf;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                position = i;
            }
            result[i] = i - position;
        }
        
        // Right to left pass
        position = inf;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                position = i;
            }
            result[i] = Math.min(result[i], position - i);
        }
        
        return result;
    }
}

Time Complexity

This approach ensures an efficient solution to the problem while maintaining clarity and simplicity.

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