223. Shortest Word Distance
You are given words, an array of strings, together with two target strings word1 and word2. Both targets are guaranteed to appear somewhere in the array, and they are guaranteed to be different words.
Return the smallest possible value of |i - j|, where words[i] equals word1 and words[j] equals word2 — in other words, how close the two words ever get to each other in the array. Either word may occur many times; you are free to pair any occurrence of one with any occurrence of the other.
Example 1:
Input: words = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3
Explanation: "coding" sits at index 3 and "practice" at index 0, so the gap is |3 - 0| = 3.
Example 2:
Input: words = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1
Explanation: "makes" occurs at indices 1 and 4; pairing index 4 with "coding" at index 3 gives a gap of 1.
Constraints:
- 2 ≤ words.length ≤ 3 * 10⁴
- 1 ≤ words[i].length ≤ 10
- words[i] consists of lowercase English letters
- word1 and word2 both appear in words
- word1 ≠ word2
Hints:
The direct route: collect every index of word1 and every index of word2, then compare all pairs. It works, but a word repeated many times makes it quadratic.
One pass is enough. As you scan, remember the most recent index where you saw word1 and the most recent index where you saw word2 — whenever both have been seen, their current gap is a candidate answer.
Why does the last-seen trick capture the optimum? For any occurrence, the nearest partner on its left is the most recent one, so every optimal pair is examined the moment its second member is scanned.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Expected output: 3