Shortest Distance to a Character

1 min readUpdated 23 June 2025

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:

EXAMPLE_ENTITY

s = "appleorange", c = "a"

Output:

EXAMPLE_ENTITY

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

Explanation:

EXAMPLE_ENTITY

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:

EXAMPLE_ENTITY

s = "banana", c = "b"

Output:

EXAMPLE_ENTITY

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

Explanation:

EXAMPLE_ENTITY

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:

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.
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
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;
    }
}
Powered by Vultr AgentBeta

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.

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Shortest Distance to a Character

1 min readUpdated 23 June 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

s = "appleorange", c = "a"

Output:

EXAMPLE_ENTITY

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

Explanation:

EXAMPLE_ENTITY

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:

EXAMPLE_ENTITY

s = "banana", c = "b"

Output:

EXAMPLE_ENTITY

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

Explanation:

EXAMPLE_ENTITY

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:

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.
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
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;
    }
}
Powered by Vultr AgentBeta

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.

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.