diff options
author | Jack Sangdahl <[email protected]> | 2024-06-11 13:27:03 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-12 01:39:13 -0600 |
commit | a7246d50a218fa673bf76ed9df7c26caaed883d3 (patch) | |
tree | f08662fb54e0bd54d7f65f410aad83c82d319fcb /lex_smallest_beaut_str.c | |
parent | 4ada2a99189b5fb1f752992116c77179ef92fa1f (diff) | |
download | leetcode-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.c | 47 |
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); +} |