Shortest gap between revisits
A dispatcher reviews a delivery route recorded as the sequence of stop codes the van visited, in order. A van that returns to a stop soon after leaving it wastes time, so the dispatcher wants the smallest number of steps between any two visits to the same stop, where the number of steps is the difference between the two positions in the sequence. Read the number of stops and then the stop codes, one per line, and print that minimum, or none if no stop is visited twice.
Input
The first line is N. Each of the next N lines is a stop code (1-10 characters, letters and digits, case-sensitive).
Output
One line: the smallest gap as an integer, or none.
Example 1
Input
6 A B C A B A
Output
2
A is visited at positions 0, 3 and 5 (gaps 3 and 2) and B at 1 and 4 (gap 3); the smallest gap is 2.
Example 2
Input
7 D7 d7 D7 E2 E2 F1 D7
Output
1
D7 and d7 are different codes. E2 appears at positions 3 and 4, so the answer is 1.
Constraints
- 1 <= N <= 200000
- Stop codes have 1-10 characters
Hints
Hint 1 of 3
Comparing every pair of positions is O(N^2), far too slow for 200000 stops. You only ever need each stop's most recent position.
Hint 2 of 3
Keep a HashMap<String, usize> from stop code to the last position it was seen at; on every visit, if the code is already in the map the gap is position - previous.
Hint 3 of 3
After computing the gap, overwrite the stored position with the current one: the next visit's smallest gap is always to the most recent visit, never to an earlier one. Use Option<usize> for the best gap so none is a real state, not a magic number.
Solution
Show a reference solution and explanation
use std::collections::HashMap;
use std::io::{self, BufRead};
fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
let mut last_seen: HashMap<String, usize> = HashMap::new();
let mut best: Option<usize> = None;
for position in 0..n {
let stop = lines.next().unwrap().unwrap().trim().to_string();
if let Some(&previous) = last_seen.get(&stop) {
let gap = position - previous;
best = Some(match best {
Some(current) if current <= gap => current,
_ => gap,
});
}
last_seen.insert(stop, position);
}
match best {
Some(gap) => println!("{}", gap),
None => println!("none"),
}
}
Why it works
The key observation is that for any stop, the smallest gap between two of its visits is always between two consecutive visits, so it is enough to remember the latest position of every stop. A HashMap gives that lookup and update in expected constant time, making the whole pass O(N). The map's iteration order is never used, only lookups, which is why a HashMap is safe here where an ordered output would have called for a BTreeMap. Option<usize> models no repeat yet honestly: the final match prints either the number or none, and there is no risk of confusing a placeholder such as 0 with a real gap.