Ward Scanner Cut Marks
String cuts minimizing dictionary costs, piece count, then lexicographic order
A hospital ward scanner records supply labels without separators. Its recorded string is scan. The ward has a catalog of recognized labels in codes, where using catalog entry i incurs the verification cost costs[i].
Split the entire scan into consecutive, nonempty pieces. Each piece must exactly equal a catalog code. A catalog entry may be used any number of times. If the same code appears more than once in the catalog, any of those entries may be used, with its corresponding cost.
Choose a split using these priorities, in order:
- Minimize the total verification cost.
- Among splits with that cost, minimize the number of pieces.
- Among remaining splits, choose the lexicographically smallest list of cut positions.
Return the cut positions as an increasing list of exclusive end indices, including the end of the scan. For example, cut positions [2, 5] describe pieces scan[0:2] and scan[2:5]. For lexicographic comparison, the list with the smaller value at the first differing position comes first.
Return [-1] if the scan cannot be fully split into recognized labels. An empty scan requires no pieces, so return [].
Examples
Example 1
Input: scan = "abac", codes = ["a","b","c","ab","ac"], costs = [1,1,1,2,2] Output: [2,4]
The scan can be split as `ab` followed by `ac`, or as `a`, `b`, `a`, `c`. Both have the same total cost, so the split with two pieces is preferred.
Example 2
Input: scan = "abc", codes = ["a","bc","ab","c"], costs = [1,2,2,1] Output: [1,3]
Splitting as `a` followed by `bc` and splitting as `ab` followed by `c` have equal cost and equal piece count. The former has the smaller first cut position and is selected.
Example 3
Input: scan = "abz", codes = ["a","b","ab"], costs = [2,2,3] Output: [-1]
No recognized code contains the final letter `z`, so no split can cover the entire scan.
Constraints
- 0 <= scan.length <= 10000
- 0 <= codes.length <= 2000
- costs.length == codes.length
- 1 <= codes[i].length <= 32
- The sum of all code lengths is at most 20000.
- scan and every code contain only lowercase English letters.
- 1 <= costs[i] <= 1000000
- Duplicate codes are allowed.
The intended solution takes O(S + nL) time and O(S + n) space, where S is the total catalog length, n is the scan length, and L is the maximum code length. Cut positions refer to string indices, not catalog indices.
Hints
Show hint 1Hint 1
Store the codes in a trie, retaining the cheapest cost at each terminal node. From a scan position, traversal reveals every recognized piece starting there.
Show hint 2Hint 2
Process suffixes from right to left. Compare candidate splits by total cost, piece count, and first cut position; the chosen suffix already supplies the canonical continuation.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the minimum total cost and the chosen catalog entry indices as well, using the smallest catalog index to resolve duplicate-code ties?
- How would the approach change if each catalog entry could be used at most once?
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