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 | |
parent | 4ada2a99189b5fb1f752992116c77179ef92fa1f (diff) | |
download | leetcode-a7246d50a218fa673bf76ed9df7c26caaed883d3.tar.gz leetcode-a7246d50a218fa673bf76ed9df7c26caaed883d3.zip |
2663. lexicographically smallest beautiful string
-rw-r--r-- | lex_smallest_beaut_str.c | 47 | ||||
-rw-r--r-- | lex_smallest_beaut_str.py | 36 |
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)) |