Bus Itinerary Tail Repairs
Earliest archive index minimizing end deletions and appends per query string
A city bus dispatcher keeps an archive of itinerary codes. Each lowercase letter represents one stop, and the letters in a code give the stops in visiting order. A stop may appear more than once. The empty code represents a bus that stays at the depot.
To turn an archived itinerary into a requested itinerary, the dispatcher may perform either of these operations, each costing one repair:
- Remove the last stop from the current itinerary, if it is nonempty.
- Append any one stop to the end of the current itinerary.
Stops cannot be inserted, removed, or replaced in the middle.
For each string in requests, choose the entry in archive that can be turned into that request using the fewest repairs. If several archive entries require the same minimum number of repairs, choose the one with the smallest zero-based archive index. Duplicate archive entries are allowed and keep their separate indices.
Return the chosen archive indices in the same order as requests. The archive does not change while requests are processed.
Examples
Example 1
Input: archive = ["ab","abca","abc","xy"], requests = ["abcd","xy"] Output: [2,3]
For the first request, the archive entry that already follows its first three stops needs only one appended stop. For the second request, an exact archive match needs no repairs.
Example 2
Input: archive = ["","abc","abca","z"], requests = ["","ab"] Output: [0,1]
The empty request is closest to an empty archived itinerary. For the other request, removing its archived final stop is cheaper than rebuilding from the depot.
Example 3
Input: archive = ["abx","aby","a","abx"], requests = ["ab","abz","abx"] Output: [0,0,0]
Some requests have multiple equally good choices. The tie is resolved by archive index, not by alphabetical order or by preferring fewer deletions.
Constraints
- 1 <= archive.length <= 2000
- 0 <= requests.length <= 2000
- 0 <= length of each itinerary code <= 80
- Every itinerary code contains only lowercase English letters.
- The sum of the lengths of all archive codes is at most 17000.
- The sum of the lengths of all request codes is at most 17000.
The intended solution takes O(A + R + n + m) time and O(A + n) auxiliary space, where A and R are the total archive and request lengths, and n and m are their entry counts. When evaluating a cached entry at depth d, its actual common prefix may be longer than d, so that candidate score can overestimate its true distance. It never underestimates it, and every optimal entry is represented by an equally good or better cached entry at its true common-prefix depth. This also preserves the specified index tie-break.
Hints
Show hint 1Hint 1
If two itineraries have lengths a and b and a longest common prefix of length p, how many tail repairs are necessary?
Show hint 2Hint 2
Build a trie of archived itineraries. At each node, retain the shortest archived itinerary in its subtree, breaking equal-length ties by archive index. Consider these retained entries along a request's matching trie path.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the number of repairs for each chosen entry?
- How would you support adding archived itineraries between requests while preserving the same query-time complexity?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem