Production House Spotlight Order
Lexicographically smallest array subsequence with each distinct string once
A film festival has an ordered queue of promotional reels. Each reel belongs to a production house, identified by a lowercase name in houses.
The festival wants a shorter spotlight program containing exactly one reel from every production house that appears in the queue. Reels may be skipped, but the selected reels must keep their original relative order.
Return the lexicographically smallest possible list of production-house names for the spotlight program.
To compare two lists lexicographically, compare their names at the first position where they differ. The list with the alphabetically smaller name at that position is smaller. Names use ordinary lowercase string ordering: a shorter name precedes a longer name when it is a prefix of that name.
Return the names, not the reel indices. If the queue is empty, return an empty list.
Examples
Example 1
Input: houses = ["cedar","birch","cedar","aster","birch","aster"] Output: ["birch","cedar","aster"]
Starting with aster would leave no way to include cedar afterward. Starting with birch is feasible because a later cedar reel remains, and an aster reel can follow it.
Example 2
Input: houses = ["moss","ember","moss"] Output: ["ember","moss"]
The later moss reel makes it possible to skip the opening moss reel and begin with the alphabetically earlier ember house.
Example 3
Input: houses = ["lumen","lumen","lumen"] Output: ["lumen"]
There is only one distinct production house, so the spotlight program contains that house once.
Constraints
- 0 <= houses.length <= 6000
- Each house name contains between 1 and 8 lowercase English letters.
With names bounded to eight characters, the reference solution runs in O(n) time and uses O(u) auxiliary space, where u is the number of distinct houses. Different reel selections can produce the same name list; only that uniquely determined minimum list is returned.
Hints
Show hint 1Hint 1
Record the final position where each production house appears. This tells you whether a selected house could be moved to a later reel.
Show hint 2Hint 2
Maintain the selected names in a stack. Before adding a new house, consider removing larger names from the end, but only when they can still be selected later.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you adapt the solution to return reel indices, breaking ties between identical name sequences by the lexicographically smallest index sequence?
- If the queue arrives as a stream that cannot be replayed, what information would you need in advance to make the same choices?
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