diff options
-rw-r--r-- | lex_min_str_rem_star.c | 141 | ||||
-rw-r--r-- | lex_min_str_rem_star.py | 46 |
2 files changed, 187 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 +} diff --git a/lex_min_str_rem_star.py b/lex_min_str_rem_star.py new file mode 100644 index 0000000..04e2cd0 --- /dev/null +++ b/lex_min_str_rem_star.py @@ -0,0 +1,46 @@ +# 3170. Lexicographically Minimum String After Removing Stars +from queue import PriorityQueue + +""" +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. +""" + + +class Solution(object): + def clearStars(self, s): + """ + :type s: str + :rtype: str + """ + pq = PriorityQueue() + idx = [[] for i in range(26)] + remove_set = set() + for i in range(len(s)): + if s[i] == "*": + remove_set.add(i) + c = pq.get() + pq.put(c) + remove_set.add(idx[ord(c) - ord("a")][-1]) + del idx[ord(c) - ord("a")][-1] + if len(idx[ord(c) - ord("a")]) == 0: + pq.get() + continue + if len(idx[ord(s[i]) - ord("a")]) == 0: + pq.put(s[i]) + idx[ord(s[i]) - ord("a")].append(i) + ans = "" + for i in range(len(s)): + if i not in remove_set: + ans += str(s[i]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.clearStars(s="aaba*")) + print(obj.clearStars(s="abc")) |