Lexicographically Smallest Beautiful String
A string is beautiful if:
- It consists of the first
kletters of the English lowercase alphabet. - It does not contain any substring of length
2or more which is a palindrome.
You are given a beautiful string s of length n and a positive integer k.
Return the lexicographically smallest string of length n, which is larger than s and is beautiful. If there is no such string, return an empty string.
A string a is lexicographically larger than a string b of the same length if, in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.
Example 1
Input
s = "abcz", k = 26Output
"abda"The string "abda" is beautiful and lexicographically larger than "abcz", and no smaller valid beautiful string larger than "abcz" exists.
Example 2
Input
s = "dc", k = 4Output
""There is no beautiful string that is lexicographically larger than "dc".
Constraints
- 1 <= n == s.length <= 10^5
- 4 <= k <= 26
- s is a beautiful string.