aboutsummaryrefslogtreecommitdiff
path: root/construct_string_repeat_lim.c
diff options
context:
space:
mode:
authorJack Sangdahl <jack@pngu.org>2024-12-16 18:27:39 -0700
committerJack Sangdahl <jack@pngu.org>2024-12-16 18:27:39 -0700
commit9e17c0037d8a229d30c54e1b96894ff0642347db (patch)
treefab6155faec88b6e1819ec7f8f4877bc15c06613 /construct_string_repeat_lim.c
parent40e1ecd63a4842aae720d979c0d7b19ccccf8357 (diff)
downloadleetcode-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.c61
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);
+}