diff options
Diffstat (limited to 'lex_smallest_beaut_str.py')
-rw-r--r-- | lex_smallest_beaut_str.py | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/lex_smallest_beaut_str.py b/lex_smallest_beaut_str.py new file mode 100644 index 0000000..58e1381 --- /dev/null +++ b/lex_smallest_beaut_str.py @@ -0,0 +1,36 @@ +# 2663. Lexicographically Smallest Beautiful String + +""" +a string is beautiful if it consists of the first 'k' letters of the english +lowercase alphabet, it does not contain a palindrome of length 2 or 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. +""" + + +class Solution(object): + def smallestBeautifulString(self, s, k): + """ + :type s: str + :type k: int + :rtype: str + """ + ans = [ord(c) - ord("a") for c in s] + n = len(ans) - 1 + while n >= 0: + ans[n] += 1 + if ans[n] == k: + n -= 1 + elif ans[n] not in ans[max(n - 2, 0) : n]: + for j in range(n + 1, len(ans)): + ans[j] = min({0, 1, 2} - set(ans[max(0, j - 2) : j])) + return "".join(chr(ord("a") + i) for i in ans) + return "" + + +if __name__ == "__main__": + obj = Solution() + print(obj.smallestBeautifulString(s="abcz", k=26)) + print(obj.smallestBeautifulString(s="dc", k=4)) |