Minimum distance between two characters in a string
Filed under Microsoft
Free read 2 of 3Find all indices for 'a' and 'b' and compute pairwise distances in O(len(a) * len(b)).
The question
Given a string s and two target characters a and b, find the minimum distance between any occurrence of a and b. Distance is defined as the absolute difference between their 0-based indices. Return -1 if either character is not present.
Constraints
- 1 <= len(s) <= 10^5
- s contains printable ASCII characters.
- Characters a and b can be identical or distinct.
Examples
- Input
- s = "geeksforgeeks", a = 'e', b = 'k'
- Output
- 1
- Why
- 'e' is at index 1 and 'k' is at index 3 (dist 2); 'e' is also at index 2, distance to 'k' at index 3 is 1.
- Input
- s = "hello", a = 'h', b = 'z'
- Output
- -1
- Why
- 'z' is not present in the string.
Approach
Find all indices for 'a' and 'b' and compute pairwise distances in O(len(a) * len(b)).
Traverse s tracking the most recent index seen for 'a' and 'b'. Whenever one is found, update min_dist with the other's last position.
If a and b are identical, track the previous occurrence of that character and compute the distance between consecutive occurrences.
Solution
O(n) time, O(1) space
class Solution:
def minDistance(self, s: str, a: str, b: str) -> int:
if a == b:
prev = -1
min_dist = float('inf')
for i, ch in enumerate(s):
if ch == a:
if prev != -1:
min_dist = min(min_dist, i - prev)
prev = i
return min_dist if min_dist != float('inf') else -1
last_a, last_b = -1, -1
min_dist = float('inf')
for i, ch in enumerate(s):
if ch == a:
last_a = i
if last_b != -1:
min_dist = min(min_dist, last_a - last_b)
elif ch == b:
last_b = i
if last_a != -1:
min_dist = min(min_dist, last_b - last_a)
return min_dist if min_dist != float('inf') else -1
Tips
- What they are testing: Tests one-pass traversal techniques and maintaining state pointers without extra memory.
- Common mistake: Iterating through all pairs of indices leading to an O(n^2) time complexity.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.