diff options
author | Jack Sangdahl <jack@pngu.org> | 2024-12-16 18:27:39 -0700 |
---|---|---|
committer | Jack Sangdahl <jack@pngu.org> | 2024-12-16 18:27:39 -0700 |
commit | 9e17c0037d8a229d30c54e1b96894ff0642347db (patch) | |
tree | fab6155faec88b6e1819ec7f8f4877bc15c06613 /construct_string_repeat_lim.c | |
parent | 40e1ecd63a4842aae720d979c0d7b19ccccf8357 (diff) | |
download | leetcode-9e17c0037d8a229d30c54e1b96894ff0642347db.tar.gz leetcode-9e17c0037d8a229d30c54e1b96894ff0642347db.zip |
2182. construct string with repeat limit
Diffstat (limited to 'construct_string_repeat_lim.c')
-rw-r--r-- | construct_string_repeat_lim.c | 61 |
1 files changed, 61 insertions, 0 deletions
diff --git a/construct_string_repeat_lim.c b/construct_string_repeat_lim.c new file mode 100644 index 0000000..6f0f69c --- /dev/null +++ b/construct_string_repeat_lim.c @@ -0,0 +1,61 @@ +// 2182. Construct String With Repeat Limit +#include "leetcode.h" + +/* + * you are given a string 's' and an integer 'repeatLimit'. construct a new + * string 'repeatLimitedString' using the characters of 's' such that no letter + * appears more than 'repeatLimit' times in a row. you do not have to use all + * characters from 's'. return the lexicographically largest + * 'repeatLimitedString' possible. a string 'a' is lexicographically larger than + * string 'b' if in the first position where 'a' and 'b' differ, string 'a' has + * a letter that appears later in the alphabet than the corresponding letter in + * 'b'. if the first 'min(a.len, b.len)' characters do not differ, then the + * longer string is the lexicographically larger one + */ + +int *get_cnt(char *s) { + int n = strlen(s); + int *cnt = (int *)calloc(26, sizeof(int)); + for (int i = 0; i < n; i++) + cnt[s[i] - 'a']++; + return cnt; +} + +char *repeatLimitedString(char *s, int repeatLimit) { + int n = strlen(s), *cnt = get_cnt(s), idx = 0; + char *ans = (char *)calloc(n + 1, sizeof(char)); + for (int i = 'z' - 'a'; i >= 0;) { + if (!cnt[i]) { + i--; + continue; + } + char c = i + 'a'; + if (!idx || ans[idx - 1] != c) { + int copy = cnt[i] <= repeatLimit ? cnt[i] : repeatLimit; + memset(&ans[idx], c, copy); + idx += copy; + cnt[i] -= copy; + } else { + int next = i - 1; + while (next >= 0 && !cnt[next]) + next--; + if (next < 0) + break; + else { + ans[idx++] = next + 'a'; + cnt[next]--; + } + } + } + ans[idx] = '\0'; + return ans; +} + +int main() { + char *s1 = "cczazcc", *s2 = "aababab"; + char *rls1 = repeatLimitedString(s1, 3); + char *rls2 = repeatLimitedString(s2, 2); + printf("%s\n", rls1); // expect: "zzcccac" + printf("%s\n", rls2); // expect: "bbabaa" + free(rls1), free(rls2); +} |