The k-th Lexicographical String of All Happy Strings of Length n
Real-world version: Ranked Beacon BurstThe statement here is our own: the same inputs, outputs and technique.
A harbour beacon marks a shipping lane by showing a burst of length flashes, one after the other. Every flash goes out through one of three coloured filters, recorded as "b" for blue, "g" for green and "w" for white. Port rules forbid a flash from reusing the filter of the flash immediately before it, so a burst is admissible exactly when no two neighbouring flashes share a filter. The first flash of a burst may use any of the three filters.
The harbour master keeps a catalogue of every admissible burst that is exactly length flashes long. A burst is written as a string of filter letters in flash order, for example "bgb". The catalogue is arranged in dictionary order, treating "b" as earlier than "g" and "g" as earlier than "w", and the first burst in that arrangement has rank 1.
Given length and rank, return the burst sitting at that rank in the catalogue. If the catalogue for that many flashes holds fewer than rank bursts, return the empty string "".
Examples
Example 1
- Input
- length = 3, rank = 9
- Output
- "wbg"
Every neighbouring pair of flashes in `"wbg"` uses different filters, and eight admissible three-flash bursts sit ahead of it in dictionary order.
Example 2
- Input
- length = 1, rank = 4
- Output
- ""
A one-flash burst is admissible whichever filter it uses, so the catalogue for a single flash runs out before rank 4 is reached.
Example 3
- Input
- length = 2, rank = 6
- Output
- "wg"
`"wg"` is admissible because its two flashes use different filters, and five admissible two-flash bursts sit ahead of it in dictionary order.
Example 4
- Input
- length = 10, rank = 100
- Output
- "bgbwgbgbwg"
The catalogue for ten flashes runs well past rank 100, and the burst reported there changes filter at every step.
Constraints
- 1 <= length <= 10
- 1 <= rank <= 100
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def beacon_burst(length: int, rank: int) -> str:public String beaconBurst(int length, int rank)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 4 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's