Vultr DocsLatest Content

Shortest Distance to a Character

Updated on 23 June, 2025
Shortest Distance to a Character header image

Problem Statement

Given a string s and a character c that appears at least once in s, compute an array where each element represents the shortest distance from that index to any occurrence of character c. The distance between indices i and j is defined as abs(i - j) (the absolute difference).

Examples

Example 1

Input:

s = "appleorange", c = "a"

Output:

[0,1,2,3,4,5,1,0,1,2,3]

Explanation:

The character `'a'` occurs at indices 0 and 7.

* Index 0: nearest `'a'` is at 0 → distance = 0
* Index 1: nearest `'a'` is at 0 → distance = 1
* Index 6: nearest `'a'` is at 7 → distance = 1
* Index 10: nearest `'a'` is at 7 → distance = 3

...and so on.

Example 2

Input:

s = "banana", c = "b"

Output:

[0,1,2,3,4,5]

Explanation:

The character `'b'` occurs only at index 0.

All other characters compute their distance to index 0.

Constraints

  • 1 <= s.length <= 10⁴
  • s[i] and c are lowercase English letters
  • It is guaranteed that c occurs at least once in s

Approach and Intuition

To find the shortest distances efficiently:

  1. Left-to-Right Scan

    • Traverse s while tracking the last seen position of c.
    • For each index i, compute i - lastSeen if lastSeen is not None.

  2. Right-to-Left Scan

    • Do a second pass from right to left.
    • Track the next seen position of c, and update the result at index i if nextSeen - i is smaller than the current value.

This ensures each character's distance is minimized based on the closest 'c' either to its left or right.

Efficiency

  • Time Complexity: O(n)
  • Space Complexity: O(n)

This approach is optimal for large strings and avoids unnecessary lookups or nested iterations.

Solutions

  • Java
java 
class Solution {
    public int[] distanceToChar(String str, char target) {
        int length = str.length();
        int[] result = new int[length];
        int lastSeen = Integer.MIN_VALUE / 2;

        for (int i = 0; i < length; ++i) {
            if (str.charAt(i) == target) lastSeen = i;
            result[i] = i - lastSeen;
        }

        lastSeen = Integer.MAX_VALUE / 2;
        for (int i = length - 1; i >= 0; --i) {
            if (str.charAt(i) == target) lastSeen = i;
            result[i] = Math.min(result[i], lastSeen - i);
        }

        return result;
    }
}

The Java solution provided outlines an efficient method to calculate the shortest distance from each character in a given string to a specific target character. The function distanceToChar takes a string and a character as input and returns an array of integers where each element represents the minimum distance to the nearest occurrence of the target character.

  • The function initializes an array result of the same length as the input string, to store the distances.
  • It uses a variable lastSeen to keep track of the last occurrence index of the target character.
  • The first loop iterates through the string from the start to end, updating lastSeen whenever the target character is found and calculating the distance from the current index to lastSeen.
  • The second loop iterates from the end of the string back to the start. This ensures that each character in the string is compared with the nearest occurrence of the target character both before and after it.
  • The minimum distance from each character to the target is then updated in the result array using the Math.min method.

This two-pass approach ensures that all possible directions are considered for determining the shortest distance to the target character, resulting in an efficient and comprehensive solution.

Comments

No comments yet.