Construct String With Repeat Limit
Real-world version: Largest Banner Under a Run CapThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def largest_banner(tiles: str, run_cap: int) -> str:public String largestBanner(String tiles, int runCap)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 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