aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-06-11 13:27:03 -0600
committerJack Sangdahl <[email protected]>2025-06-12 01:39:13 -0600
commita7246d50a218fa673bf76ed9df7c26caaed883d3 (patch)
treef08662fb54e0bd54d7f65f410aad83c82d319fcb
parent4ada2a99189b5fb1f752992116c77179ef92fa1f (diff)
downloadleetcode-a7246d50a218fa673bf76ed9df7c26caaed883d3.tar.gz
leetcode-a7246d50a218fa673bf76ed9df7c26caaed883d3.zip
2663. lexicographically smallest beautiful string
-rw-r--r--lex_smallest_beaut_str.c47
-rw-r--r--lex_smallest_beaut_str.py36
2 files changed, 83 insertions, 0 deletions
diff --git a/lex_smallest_beaut_str.c b/lex_smallest_beaut_str.c
new file mode 100644
index 0000000..8009a4a
--- /dev/null
+++ b/lex_smallest_beaut_str.c
@@ -0,0 +1,47 @@
+// 2663. Lexicographically Smallest Beautiful String
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+char *smallestBeautifulString(char *s, int k) {
+ int n = strlen(s);
+ char *ans = (char *)malloc((n + 1) * sizeof(char));
+ strcpy(ans, s);
+ for (int i = n - 1; i >= 0; i--) {
+ for (int j = ans[i] - 'a' + 1; j < k; j++) {
+ char curr = j + 'a';
+ if ((i < 1 || curr != ans[i - 1]) && (i < 2 || curr != ans[i - 2])) {
+ ans[i] = curr;
+ for (int l = i + 1; l < n; l++) {
+ for (int m = 0; m < k; m++) {
+ curr = m + 'a';
+ if ((l < 1 || curr != ans[l - 1]) &&
+ (l < 2 || curr != ans[l - 2])) {
+ ans[l] = curr;
+ break;
+ }
+ }
+ }
+ return ans;
+ }
+ }
+ }
+ return "";
+}
+
+int main() {
+ char *s1 = "abcz", *s2 = "dc";
+ char *sbs1 = smallestBeautifulString(s1, 26);
+ char *sbs2 = smallestBeautifulString(s2, 4);
+ printf("%s\n", sbs1); // expect: abda
+ printf("%s\n", sbs2); // expect: null
+ free(sbs1);
+ free(sbs2);
+}
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))