Arena Console Expedition
Fewest appends and end deletions to match k distinct input strings
An online game's training arena has a command console whose text buffer is initially empty. Each challenge has a distinct activation code in codes.
You may perform these actions:
- Append one lowercase English letter to the buffer, costing one keystroke.
- Delete the last letter of a nonempty buffer, costing one keystroke.
- Activate a challenge whose code exactly matches the current buffer, costing no keystrokes and leaving the buffer unchanged.
A challenge counts only once, even if activated repeatedly. Passing through a challenge's code does not activate it automatically.
Return the minimum number of keystrokes needed to activate exactly k distinct challenges. You may choose which challenges to activate, and the buffer may contain any text when you finish.
Examples
Example 1
Input: codes = ["a","ab","ac","bzz"], k = 2 Output: 2
Activate `a` after typing one letter, then append `b` and activate `ab`. This activates two challenges without any deletion.
Example 2
Input: codes = ["ga","gb","gc","zzzz"], k = 3 Output: 6
Choose `ga`, `gb`, and `gc`. Type the first code, then replace its last letter twice using one deletion and one append each time. Returning to the empty buffer is unnecessary.
Example 3
Input: codes = ["raid","ra","raven"], k = 1 Output: 2
Only one challenge is required. Typing and activating `ra` is cheaper than activating either longer code.
Constraints
- 0 <= codes.length <= 500
- Every code contains between 1 and 16 lowercase English letters.
- All codes are distinct.
- 0 <= k <= min(30, codes.length)
No challenges are activated automatically. Selecting a code does not force selection of a shorter code that is its prefix. With L equal to the total length of all codes, the reference solution uses O(L * k^2) time and O(L * k) space as upper bounds.
Hints
Show hint 1Hint 1
Represent console buffers that are prefixes of activation codes as trie nodes. Appending and deleting correspond to traversing trie edges.
Show hint 2Hint 2
For each subtree and selected challenge count, track both the cheapest walk that returns to its root and the cheapest walk that may finish inside it. When merging children, at most one child can contain the final endpoint.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the transition costs change if appending a letter and deleting a letter had different fixed costs?
- How would you reconstruct one optimal sequence of console actions, including which challenges to activate?
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