aboutsummaryrefslogtreecommitdiff
path: root/lex_smallest_beaut_str.py
diff options
context:
space:
mode:
Diffstat (limited to 'lex_smallest_beaut_str.py')
-rw-r--r--lex_smallest_beaut_str.py36
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))