Show problems as
Classic problem #2663HardStringGreedy

Lexicographically Smallest Beautiful String

Real-world version: Next Tidy Tape Over k Letters
Tracked in this browser only
Read Lexicographically Smallest Beautiful String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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

Python
def smallest_beautiful_string(s: str, k: int) -> str:
Java
public String smallestBeautifulString(String s, int k)

More on the same topics