โ† Microsoft questions
CodingReported in a candidate post, Aug 2012

Minimum distance between two characters in a string

Filed under Microsoft

Free read 2 of 3

Find 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

  1. Find all indices for 'a' and 'b' and compute pairwise distances in O(len(a) * len(b)).

Solution

O(n) time, O(1) space

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