diff options
author | Jack Sangdahl <[email protected]> | 2025-06-06 19:11:26 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-06 19:11:26 -0600 |
commit | 38025a19a342cb266e766e8cf9aeadfccd8c68ae (patch) | |
tree | ff64ade408c383da842195bfcdac5162a1ac334d /lex_min_str_rem_star.c | |
parent | 285b89a7d901268035bc0faf199b7a5c64f5d787 (diff) | |
download | leetcode-38025a19a342cb266e766e8cf9aeadfccd8c68ae.tar.gz leetcode-38025a19a342cb266e766e8cf9aeadfccd8c68ae.zip |
3170. lexicographically minimum string after removing stars
Diffstat (limited to 'lex_min_str_rem_star.c')
-rw-r--r-- | lex_min_str_rem_star.c | 141 |
1 files changed, 141 insertions, 0 deletions
diff --git a/lex_min_str_rem_star.c b/lex_min_str_rem_star.c new file mode 100644 index 0000000..1a854ef --- /dev/null +++ b/lex_min_str_rem_star.c @@ -0,0 +1,141 @@ +// 3170. Lexicographically Minimum String After Removing Stars +#include "leetcode.h" + +/* + * you are given a string 's'. it may contain any number of '*' characters. your + * task to remove all '*' characters. while there is a '*' character, do the + * following: delete the leftmost '*' and the smallest non-'*' character to its + * left. if there are several smallest characters, you can delete any of them. + * return the lexicographically smallest resulting string after removing all '*' + * characters. + */ + +struct node { + char c; + int idx; +}; + +struct pq { + int (*cmp)(const void *, const void *); + int size; + int capacity; + void **data; +}; + +struct node *node_init(char c, int idx) { + struct node *obj = (struct node *)malloc(sizeof(struct node)); + obj->c = c; + obj->idx = idx; + return obj; +} + +int cmp(const void *a, const void *b) { + char c1 = ((struct node *)a)->c; + char c2 = ((struct node *)b)->c; + int n1 = ((struct node *)a)->idx; + int n2 = ((struct node *)b)->idx; + if (c1 < c2) + return 1; + if (c1 > c2) + return -1; + if (n1 > n2) + return 1; + if (n1 < n2) + return -1; + return 0; +} + +struct pq *pq_init(int capacity, int (*cmp)(const void *, const void *)) { + struct pq *obj = (struct pq *)malloc(sizeof(struct pq)); + obj->cmp = cmp; + obj->size = 0; + obj->capacity = capacity; + obj->data = (void **)malloc(capacity * sizeof(void *)); + for (int i = 0; i < capacity; i++) + obj->data[i] = NULL; + return obj; +} + +void pq_swap(struct pq *obj, const int key1, const int key2) { + void *tmp = obj->data[key1]; + obj->data[key1] = obj->data[key2]; + obj->data[key2] = tmp; + return; +} + +void pq_repair_bottom(struct pq *obj) { + int child = obj->size - 1, parent = (child - 1) / 2; + while (child > 0 && obj->cmp(obj->data[child], obj->data[parent]) == 1) { + pq_swap(obj, child, parent); + child = parent; + parent = (child - 1) / 2; + } + return; +} + +void pq_push(struct pq *obj, void *item) { + assert(obj->size < obj->capacity); + obj->data[obj->size++] = item; + pq_repair_bottom(obj); + return; +} + +void pq_repair_top(struct pq *obj) { + int parent = 0, child = parent * 2 + 1; + while (child < obj->size) { + if (child + 1 < obj->size && + obj->cmp(obj->data[child + 1], obj->data[child]) == 1) + child++; + if (obj->cmp(obj->data[parent], obj->data[child]) == 1) + break; + pq_swap(obj, parent, child); + parent = child; + child = parent * 2 + 1; + } + return; +} + +void *pq_pop(struct pq *obj) { + assert(obj->size > 0); + pq_swap(obj, 0, obj->size - 1); + obj->size--; + pq_repair_top(obj); + return obj->data[obj->size]; +} + +void pq_free(struct pq *obj) { + for (int i = 0; i < obj->size; i++) + free(obj->data[i]); + free(obj->data); + free(obj); + return; +} + +char *clearStars(char *s) { + const int n = strlen(s); + char *ans = (char *)malloc((n + 1) * sizeof(char)); + struct pq *pq = pq_init(n, cmp); + for (int i = 0; i < n; i++) { + if (s[i] != '*') { + struct node *n = node_init(*(s + i), i); + pq_push(pq, n); + } else if (pq->size > 0) { + struct node *curr = pq_pop(pq); + s[curr->idx] = '#'; + } + } + pq_free(pq); + int idx = 0; + for (; *s; s++) + if (*s != '#' && *s != '*') + ans[idx++] = *s; + ans[idx] = '\0'; + return ans; +} + +int main() { + char *s1 = "aaba*", *cs1 = clearStars(s1); + char *s2 = "abc", *cs2 = clearStars(s2); + printf("%s\n", cs1); // expect: aab + printf("%s\n", cs2); // expect: abc +} |