aboutsummaryrefslogtreecommitdiff
path: root/lex_smallest_beaut_str.c
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 /lex_smallest_beaut_str.c
parent4ada2a99189b5fb1f752992116c77179ef92fa1f (diff)
downloadleetcode-a7246d50a218fa673bf76ed9df7c26caaed883d3.tar.gz
leetcode-a7246d50a218fa673bf76ed9df7c26caaed883d3.zip
2663. lexicographically smallest beautiful string
Diffstat (limited to 'lex_smallest_beaut_str.c')
-rw-r--r--lex_smallest_beaut_str.c47
1 files changed, 47 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);
+}