Exchange Inventory Rehearsals
All fixed-length strings with bounded running balance and a given final balance
A stock exchange uses synthetic trading histories to rehearse an inventory monitor. Each history starts with zero shares and contains exactly steps events:
B: buy one share, increasing inventory by one.S: sell one share, decreasing inventory by one.
After every event, inventory must remain between zero and capacity, inclusive. At the end of the history, inventory must equal closing.
Return every valid history as a string, in lexicographically increasing order, with B before S. Return an empty list if no history is possible.
When steps is zero, the empty string is a valid history exactly when closing is zero.
Examples
Example 1
Input: steps = 4, capacity = 2, closing = 0 Output: ["BBSS","BSBS"]
With four events and capacity two, a history may alternate buying and selling, or buy twice before selling twice. Buying three times in a row exceeds capacity, and selling as the first event makes inventory negative.
Example 2
Input: steps = 3, capacity = 1, closing = 1 Output: ["BSB"]
Capacity one forces buys and sells to alternate. After three events, the alternating history finishes with one share.
Example 3
Input: steps = 3, capacity = 3, closing = 0 Output: []
Every event changes inventory by one, so an odd number of events cannot finish at zero shares.
Constraints
- 0 <= steps <= 18
- 0 <= capacity <= 18
- 0 <= closing <= capacity
The output can be exponential in steps. With reachability pruning, enumeration takes O((steps + 1) * (R + 1)) time, where R is the number of returned histories, and O(steps + 1) auxiliary space excluding the output.
Hints
Show hint 1Hint 1
Build a history one event at a time, trying only actions that keep the inventory within its allowed range.
Show hint 2Hint 2
Explore B before S to produce sorted results. Stop a branch if the remaining events cannot reach the required closing inventory.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you count valid histories without constructing their strings?
- How would you return only the lexicographically smallest valid history, or report that none exists?
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