0979HardStringGreedy

Next Tidy Tape Over k Letters

Tracked in this browser only

Trains the technique from

LeetCode 2663Lexicographically Smallest Beautiful String

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 tape is written over the first k letters of the alphabet. It is tidy when no stretch of two or more of its characters reads the same forwards as backwards, which comes to saying that no character matches the one directly before it and none matches the one two before it.

The tape s is tidy. Return the smallest tidy tape of the same length that is strictly larger than s when compared as text, or the empty string when there is none.

Examples

Example 1

Input: s = "abc", k = 4
Output: "abd"

Raising the last character from c gives d, which clashes with neither b nor a, so "abd" is the answer.

Example 2

Input: s = "d", k = 4
Output: ""

The single character is already the largest of the four letters, so nothing larger exists.

Example 3

Input: s = "ab", k = 4
Output: "ac"

The last character rises from b to c, giving "ac".

Constraints

1 <= s.length <= 10^5
4 <= k <= 26
s is written over the first k letters and is tidy

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 smallest_beautiful_string(s: str, k: int) -> str:

Java

public String smallestBeautifulString(String s, int k)

The intended approach

Time O(n * k) for a tape of length n over k letters.Space O(n) for the tape being built.

To be larger and as small as possible, keep as long a prefix of the tape as can be kept and raise the character just after it, then fill everything beyond as small as possible. So walk the positions from the back and, at each, try every letter above the one there; the first such letter that clashes with neither of the two characters before it is the one to raise to, and the positions before it stay as they are. Once raised, every later position takes the smallest letter that clashes with neither of its own two predecessors. With four letters or more available there is always such a letter, since only two are ever ruled out, so the filling never gets stuck. Running out of positions to raise means no larger tidy tape exists.

Pythonentry point: smallest_beautiful_string

def smallest_beautiful_string(s, k):
    letters = list(s)
    n = len(letters)
    for at in range(n - 1, -1, -1):
        start = ord(letters[at]) - 97 + 1
        picked = -1
        for code in range(start, k):
            ch = chr(97 + code)
            if at >= 1 and letters[at - 1] == ch:
                continue
            if at >= 2 and letters[at - 2] == ch:
                continue
            picked = code
            break
        if picked < 0:
            continue
        letters[at] = chr(97 + picked)
        for fill in range(at + 1, n):
            for code in range(k):
                ch = chr(97 + code)
                if fill >= 1 and letters[fill - 1] == ch:
                    continue
                if fill >= 2 and letters[fill - 2] == ch:
                    continue
                letters[fill] = ch
                break
        return "".join(letters)
    return ""

The obvious version

Build every tape of the same length over the first `k` letters, keep the tidy ones, sort them, and take the first that comes after the tape given. Exponential in the tape's length and it reasons about nothing.

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_smallest_beautiful_string(s, k):
    n = len(s)
    alphabet = [chr(97 + i) for i in range(k)]
    found = []

    def build(sofar):
        if len(sofar) == n:
            found.append("".join(sofar))
            return
        at = len(sofar)
        for ch in alphabet:
            if at >= 1 and sofar[at - 1] == ch:
                continue
            if at >= 2 and sofar[at - 2] == ch:
                continue
            sofar.append(ch)
            build(sofar)
            sofar.pop()

    build([])
    found.sort()
    for text in found:
        if text > s:
            return text
    return ""

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