0545EasyArrayString

Closest Station Calls in the Announcement Log

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A train's public-address unit keeps a log of the station codes it has called out, one code per entry, in the order they were announced. The log arrives as wordsDict, so wordsDict[i] is the code called at position i. A code may be called many times.

Given two different codes word1 and word2, both of which appear somewhere in the log, return the smallest possible value of |i - j| over positions i holding word1 and positions j holding word2.

Examples

Example 1

Input: wordsDict = ["fen", "ash", "cwm", "ash", "bly", "ash", "fen"], word1 = "fen", word2 = "bly"
Output: 2

"fen" sits at positions 0 and 6, and "bly" sits at position 4. The gaps available are 4 and 2, so the answer is 2.

Example 2

Input: wordsDict = ["mo", "mo", "ka", "ka", "ze"], word1 = "mo", word2 = "ze"
Output: 3

"mo" sits at positions 0 and 1 and "ze" sits at position 4, giving gaps of 4 and 3, so the answer is 3.

Example 3

Input: wordsDict = ["elm", "dun"], word1 = "dun", word2 = "elm"
Output: 1

"dun" is at position 1 and "elm" is at position 0. The gap is measured without regard to which came first, so it is 1.

Constraints

2 <= wordsDict.length <= 3 * 10^4
1 <= wordsDict[i].length <= 10
wordsDict[i] contains only lowercase English letters.
word1 and word2 both appear in wordsDict.
word1 != word2

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def shortest_distance(wordsDict: list[str], word1: str, word2: str) -> int:

Java

public int shortestDistance(String[] wordsDict, String word1, String word2)

The intended approach

Time O(n) in the length of the log, one pass with constant work per entry.Space O(1).

Read the log once, holding two positions: the latest place `word1` was seen and the latest place `word2` was seen. When one of the codes turns up, measure it only against the other code's stored position, since any older occurrence of that other code sits further back and therefore further away. Keep the smallest gap measured. The two codes differ, so the two stored positions never describe the same entry.

Pythonentry point: shortest_distance

def shortest_distance(wordsDict, word1, word2):
    # O(n) time, O(1) space. Walk the log once holding the latest position of
    # each of the two codes. Whenever one of them turns up, the only pair worth
    # measuring is that position against the other code's latest position,
    # because any earlier occurrence of the other code is further away.
    at1 = -1
    at2 = -1
    best = len(wordsDict)
    for i, code in enumerate(wordsDict):
        if code == word1:
            at1 = i
            if at2 >= 0 and i - at2 < best:
                best = i - at2
        elif code == word2:
            at2 = i
            if at1 >= 0 and i - at1 < best:
                best = i - at1
    return best

The obvious version

Collect the list of positions holding each code, then measure the absolute gap for every pairing of one position from the first list with one from the second, and keep the smallest.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_shortest_distance(wordsDict, word1, word2):
    spots1 = []
    spots2 = []
    for i, code in enumerate(wordsDict):
        if code == word1:
            spots1.append(i)
        if code == word2:
            spots2.append(i)
    best = None
    for a in spots1:
        for b in spots2:
            gap = a - b
            if gap < 0:
                gap = -gap
            if best is None or gap < best:
                best = gap
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in