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:

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

JavaScript Solution
Python Solution

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.

Python Solution - Two Pass

from typing import List

def shortest_to_char(s: str, c: str) -> List[int]:
  """
  Find shortest distance from each character to target character
  
  Args:
      s: Input string
      c: Target character
      
  Returns:
      List[int]: Array of shortest distances
  """
  n = len(s)
  result = [float('inf')] * n
  
  # First pass: left to right
  # Find distance to nearest c on the left (or current position)
  prev = float('-inf')
  for i in range(n):
      if s[i] == c:
          prev = i
      result[i] = min(result[i], i - prev)
  
  # Second pass: right to left
  # Find distance to nearest c on the right (or current position)
  prev = float('inf')
  for i in range(n - 1, -1, -1):
      if s[i] == c:
          prev = i
      result[i] = min(result[i], prev - i)
  
  return result

# Test cases
print('Example 1:', shortest_to_char("dailybyte", 'y'))  
# [4, 3, 2, 1, 0, 1, 0, 1, 2]

print('Example 2:', shortest_to_char("loveleetcode", 'e'))  
# [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

print('Example 3:', shortest_to_char("aaab", 'b'))  
# [3, 2, 1, 0]

print('Example 4:', shortest_to_char("abaa", 'b'))  
# [1, 0, 1, 2]

Loading Python runtime...

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:

JavaScript Alternative
Python Alternative

/**
 * 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;
}

def shortest_to_char_alternative(s: str, c: str) -> List[int]:
    """
    Alternative: Find all positions first, then calculate distances
    """
    n = len(s)
    result = []
    
    # Find all positions of c
    positions = [i for i in range(n) if s[i] == c]
    
    # For each position, find minimum distance to any position of c
    for i in range(n):
        min_dist = min(abs(i - pos) for pos in positions)
        result.append(min_dist)
    
    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:

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

Example(s)​

Solution​

JavaScript Solution - Two Pass

Output:

Python Solution - Two Pass

Output:

Alternative Solution (Find All Positions First)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Find All Positions First)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Related Problems

Takeaways