0665MediumHash TableStringGreedyHeap (Priority Queue)Counting

Largest Banner Under a Run Cap

Tracked in this browser only

Trains the technique from

LeetCode 2182Construct String With Repeat Limit

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 signmaker owns a tray of letter tiles. The string tiles spells out what the tray holds, one lowercase letter per tile, so a letter that appears four times in tiles means four separate tiles carrying that letter.

The signmaker lays tiles left to right to spell a banner. Each tile may be used at most once, tiles may be left in the tray, and the banner must never show the same letter more than run_cap times in a row. A letter may still appear more than run_cap times in the banner overall, as long as no unbroken stretch of it is longer than run_cap.

Return the lexicographically largest banner the signmaker can spell. Banner x is lexicographically larger than banner y when either y is a proper prefix of x, or at the first position where the two differ x shows the letter that comes later in the alphabet.

Examples

Example 1

Input: tiles = "cccba", run_cap = 2
Output: "ccbca"

The banner uses every tile in the tray and no letter runs for more than two positions: the stretches are `cc`, `b`, `c`, `a`.

Example 2

Input: tiles = "zzzz", run_cap = 2
Output: "zz"

The tray holds nothing but `z`, and a third `z` would make a run of three, so two tiles stay in the tray.

Example 3

Input: tiles = "ddddcc", run_cap = 3
Output: "dddcdc"

Reading the banner, the runs are `ddd`, `c`, `d`, `c`. None is longer than three and all six tiles are used.

Constraints

1 <= run_cap <= tiles.length <= 10^5
tiles consists of lowercase English letters.

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 largest_banner(tiles: str, run_cap: int) -> str:

Java

public String largestBanner(String tiles, int runCap)

The intended approach

Time O(26 * n): counting is O(n), and each of at most n placements scans down the 26 counters.Space O(n): 26 counters and a cursor, plus the collected pieces that are joined into the returned banner.

Tally the tray into 26 counters, then grow the banner one stretch at a time. Take the largest letter still in the tray and lay `run_cap` of it, or all of it if fewer remain. If that letter is now gone, move the cursor down to the next non-empty letter. If tiles of it remain, lay exactly one tile of the largest letter below it so the stretch is broken, then return to the same letter and repeat. When no letter below the capped one is left, the banner is finished.

Pythonentry point: largest_banner

def largest_banner(tiles, run_cap):
    # O(n) counting, then repeatedly extend with the largest letter still in the tray
    counts = [0] * 26
    for ch in tiles:
        counts[ord(ch) - 97] += 1
    out = []
    top = 25
    while True:
        while top >= 0 and counts[top] == 0:
            top -= 1
        if top < 0:
            break
        take = min(counts[top], run_cap)
        out.append(chr(97 + top) * take)
        counts[top] -= take
        if counts[top] == 0:
            continue
        nxt = top - 1
        while nxt >= 0 and counts[nxt] == 0:
            nxt -= 1
        if nxt < 0:
            break
        out.append(chr(97 + nxt))
        counts[nxt] -= 1
    return "".join(out)

The obvious version

Search every banner that can be spelled. The state is the tiles still in the tray, the last letter laid and how long its current stretch is; from each state try laying every letter still available whose stretch would stay inside the cap, and also try stopping. Memoise the best banner reachable from each state and return the best from the full tray.

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_largest_banner(tiles, run_cap):
    counts = [0] * 26
    for ch in tiles:
        counts[ord(ch) - 97] += 1
    memo = {}

    def best(state, last, run):
        key = (state, last, run)
        if key in memo:
            return memo[key]
        top = ""
        for c in range(25, -1, -1):
            if state[c] == 0:
                continue
            nrun = run + 1 if c == last else 1
            if nrun > run_cap:
                continue
            nxt = list(state)
            nxt[c] -= 1
            cand = chr(97 + c) + best(tuple(nxt), c, nrun)
            if cand > top:
                top = cand
        memo[key] = top
        return top

    return best(tuple(counts), -1, 0)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 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