Pular para o conteúdo principal

Shortest Distance to Character

Given a string s and a character c, return an array of integers where each index is the shortest distance from the character at that position to the nearest occurrence of c in the string.

Note: The distance is the absolute difference between indices. If the character at a position is c itself, the distance is 0.

Example(s)​

Example 1:

Input: s = "dailybyte", c = 'y'
Output: [4, 3, 2, 1, 0, 1, 0, 1, 2]
Explanation:
Character 'y' appears at indices 4 and 6.
- Index 0 ('d'): distance to y at 4 = 4, to y at 6 = 6, min = 4
- Index 1 ('a'): distance to y at 4 = 3, to y at 6 = 5, min = 3
- Index 2 ('i'): distance to y at 4 = 2, to y at 6 = 4, min = 2
- Index 3 ('l'): distance to y at 4 = 1, to y at 6 = 3, min = 1
- Index 4 ('y'): distance = 0
- Index 5 ('b'): distance to y at 4 = 1, to y at 6 = 1, min = 1
- Index 6 ('y'): distance = 0
- Index 7 ('t'): distance to y at 4 = 3, to y at 6 = 1, min = 1
- Index 8 ('e'): distance to y at 4 = 4, to y at 6 = 2, min = 2

Example 2:

Input: s = "loveleetcode", c = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
Explanation:
Character 'e' appears at indices 3, 5, 6, and 11.

Example 3:

Input: s = "aaab", c = 'b'
Output: [3, 2, 1, 0]
Explanation:
Character 'b' appears only at index 3.

Example 4:

Input: s = "abaa", c = 'b'
Output: [1, 0, 1, 2]
Explanation:
Character 'b' appears only at index 1.

Solution​

The solution uses a two-pass approach:

  1. First pass (right to left): For each position, find the distance to the nearest c on the right
  2. Second pass (left to right): For each position, find the distance to the nearest c on the left
  3. Take minimum: For each position, take the minimum of left and right distances

JavaScript Solution - Two Pass

/**
* Find shortest distance from each character to target character
* @param {string} s - Input string
* @param {character} c - Target character
* @return {number[]} - Array of shortest distances
*/
function shortestToChar(s, c) {
const n = s.length;
const result = new Array(n).fill(Infinity);

// First pass: left to right
// Find distance to nearest c on the left (or current position)
let prev = -Infinity;
for (let i = 0; i < n; i++) {
  if (s[i] === c) {
    prev = i;
  }
  result[i] = Math.min(result[i], i - prev);
}

// Second pass: right to left
// Find distance to nearest c on the right (or current position)
prev = Infinity;
for (let i = n - 1; i >= 0; i--) {
  if (s[i] === c) {
    prev = i;
  }
  result[i] = Math.min(result[i], prev - i);
}

return result;
}

// Test cases
console.log('Example 1:', shortestToChar("dailybyte", 'y')); 
// [4, 3, 2, 1, 0, 1, 0, 1, 2]

console.log('Example 2:', shortestToChar("loveleetcode", 'e')); 
// [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

console.log('Example 3:', shortestToChar("aaab", 'b')); 
// [3, 2, 1, 0]

console.log('Example 4:', shortestToChar("abaa", 'b')); 
// [1, 0, 1, 2]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Find All Positions First)​

Here's an alternative that first finds all positions of c, then calculates distances:

/**
 * Alternative: Find all positions first, then calculate distances
 */
function shortestToCharAlternative(s, c) {
  const n = s.length;
  const result = [];
  
  // Find all positions of c
  const positions = [];
  for (let i = 0; i < n; i++) {
    if (s[i] === c) {
      positions.push(i);
    }
  }
  
  // For each position, find minimum distance to any position of c
  for (let i = 0; i < n; i++) {
    let minDist = Infinity;
    for (const pos of positions) {
      minDist = Math.min(minDist, Math.abs(i - pos));
    }
    result.push(minDist);
  }
  
  return result;
}

Complexity​

  • Time Complexity:
    • Two-pass approach: O(n) - Where n is the length of the string. We make two passes through the string.
    • Alternative approach: O(n × m) - Where n is string length and m is number of occurrences of c. Less efficient when c appears many times.
  • Space Complexity: O(n) - For the result array. The two-pass approach uses O(1) extra space (excluding result).

Approach​

The solution uses a two-pass algorithm:

  1. First pass (left to right):

    • Track the last occurrence of c seen so far
    • For each position, calculate distance to the last c on the left
    • Update result with this distance

  2. Second pass (right to left):

    • Track the last occurrence of c seen so far (from right)
    • For each position, calculate distance to the nearest c on the right
    • Update result with the minimum of left and right distances

  3. Result: Each position has the minimum distance to the nearest c

Key Insights​

  • Two-pass approach: More efficient than checking all positions of c for each character
  • Track nearest occurrence: Keep track of the nearest c from each direction
  • Take minimum: For each position, take the minimum of left and right distances
  • O(n) time: Linear time complexity is optimal
  • Greedy approach: Process from both directions to find nearest occurrence

Step-by-Step Example​

Let's trace through Example 1: s = "dailybyte", c = 'y'

String:  d a i l y b y t e
Index:   0 1 2 3 4 5 6 7 8
Result:  [inf, inf, inf, inf, inf, inf, inf, inf, inf]

First pass (left to right):
  i=0: s[0]='d' ≠ 'y', prev=-inf, result[0] = min(inf, 0-(-inf)) = inf
  i=1: s[1]='a' ≠ 'y', prev=-inf, result[1] = min(inf, 1-(-inf)) = inf
  i=2: s[2]='i' ≠ 'y', prev=-inf, result[2] = min(inf, 2-(-inf)) = inf
  i=3: s[3]='l' ≠ 'y', prev=-inf, result[3] = min(inf, 3-(-inf)) = inf
  i=4: s[4]='y' == 'y', prev=4, result[4] = min(inf, 4-4) = 0
  i=5: s[5]='b' ≠ 'y', prev=4, result[5] = min(inf, 5-4) = 1
  i=6: s[6]='y' == 'y', prev=6, result[6] = min(inf, 6-6) = 0
  i=7: s[7]='t' ≠ 'y', prev=6, result[7] = min(inf, 7-6) = 1
  i=8: s[8]='e' ≠ 'y', prev=6, result[8] = min(inf, 8-6) = 2
  After first pass: [inf, inf, inf, inf, 0, 1, 0, 1, 2]

Second pass (right to left):
  i=8: s[8]='e' ≠ 'y', prev=inf, result[8] = min(2, inf-8) = 2
  i=7: s[7]='t' ≠ 'y', prev=inf, result[7] = min(1, inf-7) = 1
  i=6: s[6]='y' == 'y', prev=6, result[6] = min(0, 6-6) = 0
  i=5: s[5]='b' ≠ 'y', prev=6, result[5] = min(1, 6-5) = 1
  i=4: s[4]='y' == 'y', prev=4, result[4] = min(0, 4-4) = 0
  i=3: s[3]='l' ≠ 'y', prev=4, result[3] = min(inf, 4-3) = 1
  i=2: s[2]='i' ≠ 'y', prev=4, result[2] = min(inf, 4-2) = 2
  i=1: s[1]='a' ≠ 'y', prev=4, result[1] = min(inf, 4-1) = 3
  i=0: s[0]='d' ≠ 'y', prev=4, result[0] = min(inf, 4-0) = 4

Final: [4, 3, 2, 1, 0, 1, 0, 1, 2]

Visual Representation​

String:  d a i l y b y t e
Index:   0 1 2 3 4 5 6 7 8
         ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
         → → → → y → y → →
         ← ← ← ← y ← y ← ←
         
Distance to nearest 'y':
- Index 0: distance to y at 4 = 4
- Index 1: distance to y at 4 = 3
- Index 2: distance to y at 4 = 2
- Index 3: distance to y at 4 = 1
- Index 4: y itself = 0
- Index 5: distance to y at 4 or 6 = 1
- Index 6: y itself = 0
- Index 7: distance to y at 6 = 1
- Index 8: distance to y at 6 = 2

Edge Cases​

  • Character appears once: Works correctly
  • Character appears multiple times: Finds nearest occurrence
  • Character at start: Distance 0 at index 0
  • Character at end: Distance 0 at last index
  • Character doesn't appear: Would need to handle (but problem assumes it appears)
  • Single character string: Works correctly

Important Notes​

  • Two-pass is optimal: O(n) time complexity
  • Handles multiple occurrences: Automatically finds the nearest one
  • Direction matters: Need to check both left and right
  • Initial values: Use Infinity for initial distances
  • Character at position: Distance is 0 if character is c itself
  • Shortest Distance in a Line: Similar concept for 1D arrays
  • Shortest Path in Binary Matrix: 2D version
  • Edit Distance: Different distance metric
  • Hamming Distance: Distance between strings

Takeaways​

  • Two-pass approach is efficient and elegant
  • Track nearest occurrence from both directions
  • Take minimum of left and right distances
  • O(n) time is optimal for this problem
  • Simple algorithm but requires careful tracking of previous occurrence