JuniorCodeCommonNot answered yet
Shortest distance between an X and a Y in a string
Given a string of 'X', 'Y', and 'O', return the shortest distance between any 'X' and any 'Y', where adjacent positions are distance 1. Return 0 if either letter is absent.
Requirements:
- O(n) time, O(1) extra space — a single pass.
int shortestXY(const std::string& s) {
// your code here
}Write the implementation.
Sweep once keeping the last seen index of X and of Y. On an X, if a Y was seen, update the minimum with i - lastY; on a Y, symmetrically with i - lastX. If either letter never appears, return 0. One pass, O(n) time, O(1) space.
- ✗Updating only
lastXand notlastY(or vice versa), missing pairs in one direction - ✗Returning a stale large sentinel when one of the letters never appears instead of 0
- ✗Computing distance only from the first occurrence rather than the nearest one
- →Why is tracking just the last seen index of each letter enough?
- →How would you extend this to the shortest distance between any two of K letters?
Contents
Task
Find the shortest distance between an X and a Y in a string of X/Y/O in one pass; 0 if either letter is missing.
Solution
int shortestXY(const std::string& s) {
int lastX = -1, lastY = -1, best = INT_MAX;
for (int i = 0; i < static_cast<int>(s.size()); ++i) {
if (s[i] == 'X') {
lastX = i;
if (lastY != -1) best = std::min(best, i - lastY);
} else if (s[i] == 'Y') {
lastY = i;
if (lastX != -1) best = std::min(best, i - lastX);
}
}
return best == INT_MAX ? 0 : best; // a letter is missing
}Key points
- At each letter we update the distance to the last opposite one — enough for the nearest pair.
- We track the last index of both letters, not just one.
- If
beststaysINT_MAX, a letter is absent — return 0.
Contents
