Bakery Ranked Label Orders

Select and remove lexicographically ranked strings matching each prefix

MediumTriesOrder StatisticsSimulation

A bakery has packaged pastries, each bearing a lowercase label. Several packages may have the same label.

Customers place requests in order. Request i consists of a prefix prefixes[i] and a positive rank ranks[i]:

  1. Consider all packages still available whose labels start with that prefix.
  2. Arrange their labels in lexicographic order, counting duplicate labels separately.
  3. If there are at least ranks[i] matching packages, hand over the package at that 1-based position and remove exactly one occurrence of its label from the inventory.
  4. Otherwise, hand over nothing and leave the inventory unchanged.

Return a string array containing the label handed over for each request, or "" if that request cannot be fulfilled.

An empty prefix matches every label. Lexicographic order uses the usual ordering a < b < ... < z; when one label is a prefix of another, the shorter label comes first.

Examples

Example 1

Input: labels = ["bun","butter","bun","cake"], prefixes = ["bu","bu","","bu"], ranks = [2,2,1,1]
Output: ["bun","butter","bun",""]

The first request matches bun, bun, and butter, so its second package is labeled bun. One bun remains. The next request receives butter, the empty-prefix request receives bun, and the final request has no remaining match.

Example 2

Input: labels = ["a","aa","ab","b"], prefixes = ["a","a","a","a"], ranks = [1,2,2,1]
Output: ["a","ab","","aa"]

Among labels starting with a, a comes before aa and ab. After a is handed over, the second remaining match is ab. The next rank is too large, so nothing changes; the last request can still receive aa.

Example 3

Input: labels = ["roll","roll"], prefixes = ["r","r","r"], ranks = [2,2,1]
Output: ["roll","","roll"]

Both packages have the same label but occupy separate ranked positions. The first request removes one of them. The second request fails because only one remains, and the third request removes that last package.

Constraints

  • 0 <= labels.length <= 2500
  • 0 <= prefixes.length == ranks.length <= 2500
  • 1 <= labels[i].length <= 20
  • 0 <= prefixes[i].length <= 20
  • Labels and prefixes contain only lowercase English letters.
  • 1 <= ranks[i] <= 1000000000
  • The sum of the lengths of all labels is at most 50000.

Duplicate packages with identical labels are indistinguishable: removing any one of them produces the same inventory. A failed request never consumes a package. The intended solution uses O(S + Q · A · L) time and O(S) space, where S is the total input-label length, Q is the number of requests, A = 26, and L is the maximum label or prefix length.

Hints

Show hint 1

A trie node can store both the number of labels ending there and the total number of available packages in its subtree.

Show hint 2

After reaching a request's prefix, treat terminal occurrences and child subtrees as consecutive lexicographic blocks. Skip whole blocks to locate the requested rank.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you support requests that add new packages between customer orders?
  • How would you change the counts if each distinct available label occupied only one ranked position, regardless of its package count?

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