Market Street Errand
On Saturdays a long street turns into a market. The stalls stand in one row, and each sells a single kind of thing, written as a letter: b for bread, h for honey, e for eggs. Several stalls can sell the same thing. The street, read from one end, is a string like "ebxhbqe".
Your shopping list, wanted, is also written as letters, and each stall sells you one item. Your bags are heavy, so you want to walk the shortest unbroken section of the street where you can buy everything on the list.
Your task
Write shortestErrand(street, wanted). Return the shortest substring of street that contains every character of wanted, including repeats: if wanted has two h's, the substring needs at least two h's. Extra stalls inside the section are fine.
If several substrings tie for shortest, return the one that starts first (leftmost). If no section works, return the empty string "". Letters are case-sensitive.
shortestErrand(street: string, wanted: string) → string
Examples
street = "ebxhbqe" wanted = "hbe"
"ebxh"
The section ebxh (stalls 0 to 3) has e, b and h, length 4. The section hbqe (stalls 3 to 6) also has all three, but it is also length 4 and starts later. Nothing shorter works: every 3-stall section is missing at least one item.
street = "hbhxxeh" wanted = "hhe"
"hxxeh"
The list needs two h's and an e. hbhxxe (length 6) works, but hxxeh (stalls 2 to 6, length 5) is shorter. Counting only the kinds of item, and not how many, would wrongly accept eh.
Constraints
- 0 ≤ street.length ≤ 10,000
- 1 ≤ wanted.length ≤ 1,000
- street and wanted contain letters a-z and A-Z only.
Start with brute force
Try every start and every end, count the letters in that section, and check them against the list. Or, slightly better, try each length from 1 upward and stop at the first length where some section works.
There are about 50 million sections in a 10,000-stall street, and each check costs more work. Even the smarter version recounts overlapping sections over and over, when a section and its neighbour differ by just one stall.
Hints
0 of 4 shown- Hint 1
In the first example, walk from the start until you have everything: that happens at stall 3, with section
ebxh. Could you drop the first stall and still have everything? What does that tell you about where to look next? - Hint 2
Every valid section ends somewhere. For each end position, you want the latest start that still covers the list. As the end moves right, that best start never moves left.
- Hint 3
So use a window: move the right edge one stall at a time. When the window covers the list, pull the left edge in as far as it stays covering, record it, then pull once more to break it and continue.
- Hint 4
To check "covers the list" in O(1), keep
need: how many of each letter the list still wants, andmissing: how many list items are still uncovered. When a stall enters andneed[c] > 0, decreasemissing. Decreaseneed[c]either way. Whenmissingis 0, shrink from the left, adding backneedand increasingmissingwhen it goes above 0. Only record a window if it is strictly shorter, which keeps the leftmost tie.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Slide a window over the street. The right edge adds stalls until the window covers the list. Then the left edge removes stalls for as long as the window still covers it, because each removal gives a shorter candidate. The moment it stops covering, go back to growing on the right.
The bookkeeping: need[c] is how many more c's the window still wants (negative means it has spares), and missing is the total still wanted. The window covers the list exactly when missing is 0.
Trace "ebxhbqe" with list "hbe" (need h 1, b 1, e 1, missing 3):
- Add e (stall 0): wanted, missing 2. Add b: missing 1. Add x: not wanted, need[x] = -1.
- Add h (stall 3): missing 0. Window
ebxh, length 4. Best =ebxh. Drop e: need[e] goes back to 1, missing 1. Stop shrinking. - Add b (stall 4): need[b] was 0, so it is a spare. Missing stays 1. Add q: spare.
- Add e (stall 6): missing 0. Window
bxhbqe, length 6, not better. Drop b: it was a spare, still covering. Windowxhbqe, length 5, not better. Drop x:hbqe, length 4, ties but is not strictly shorter, so the leftmost answer stays. Drop h: missing 1. Stop.
The answer is ebxh. Each stall is added once and dropped at most once, so the total work is linear.
function shortestErrand(street, wanted) {
const need = new Map(); // letter -> how many more the window needs
for (const c of wanted) need.set(c, (need.get(c) || 0) + 1);
let missing = wanted.length;
let left = 0, bestStart = 0, bestLen = Infinity;
for (let right = 0; right < street.length; right++) {
const c = street[right];
if ((need.get(c) || 0) > 0) missing--;
need.set(c, (need.get(c) || 0) - 1);
while (missing === 0) {
if (right - left + 1 < bestLen) { bestStart = left; bestLen = right - left + 1; }
const out = street[left];
need.set(out, need.get(out) + 1);
if (need.get(out) > 0) missing++; // dropped a stall we needed
left++;
}
}
return bestLen === Infinity ? "" : street.slice(bestStart, bestStart + bestLen);
}def shortest_errand(street, wanted):
need = {} # letter -> how many more the window needs
for c in wanted:
need[c] = need.get(c, 0) + 1
missing = len(wanted)
left = best_start = 0
best_len = float('inf')
for right, c in enumerate(street):
if need.get(c, 0) > 0:
missing -= 1
need[c] = need.get(c, 0) - 1
while missing == 0:
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
out = street[left]
need[out] += 1
if need[out] > 0:
missing += 1 # dropped a stall we needed
left += 1
if best_len == float('inf'):
return ""
return street[best_start:best_start + best_len]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.