0438MediumStringBacktracking

Ranked Beacon Burst

Tracked in this browser only

Trains the technique from

LeetCode 1415The k-th Lexicographical String of All Happy Strings of Length n

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def beacon_burst(length: int, rank: int) -> str:

Java

public String beaconBurst(int length, int rank)

The intended approach

Time O(length): one pass over the flashes, each step doing constant work.Space O(length) for the burst that is built and returned.

The catalogue divides into three equal blocks by opening filter, and each later flash divides its block in two because only two filters remain available once the previous one is barred. Compare the rank against the total block size first, then walk the flashes left to right, shrinking the block size by the branching factor and reading off which sub-block the remaining offset lands in.

Pythonentry point: beacon_burst

def beacon_burst(length, rank):
    # The catalogue of admissible bursts splits into three equal blocks by
    # opening filter, and every later flash splits its block into two because
    # exactly two filters stay available once the previous one is barred. So a
    # single left-to-right walk suffices: keep the offset of the wanted burst
    # inside the current block, divide the block size by the branching factor,
    # and read off which sub-block the offset falls in.
    # O(length) time, O(length) space for the burst that is returned.
    filters = "bgw"
    total = 3 * (1 << (length - 1))
    if rank > total:
        return ""
    offset = rank - 1
    block = total // 3
    pick = offset // block
    offset -= pick * block
    burst = [filters[pick]]
    for _ in range(length - 1):
        block //= 2
        options = [f for f in filters if f != burst[-1]]
        pick = offset // block
        offset -= pick * block
        burst.append(options[pick])
    return "".join(burst)

The obvious version

Grow the whole catalogue one flash at a time, extending each burst so far by every filter that its last flash does not already use, then index the finished list. Extending in order keeps the list in dictionary order.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_beacon_burst(length, rank):
    filters = "bgw"
    bursts = [""]
    for _ in range(length):
        grown = []
        for burst in bursts:
            for f in filters:
                if burst and burst[-1] == f:
                    continue
                grown.append(burst + f)
        bursts = grown
    if rank > len(bursts):
        return ""
    return bursts[rank - 1]

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in