// 2284. Sender With Largest Word Count #include #include #include #include /* * you have a chat log of 'n' messages. you are given two string arrays * 'messages' and 'senders' where 'messages[i]' is a message sent by * 'senders[i]'. a message is a list of words that are separated by a single * space with no leading or trailing spaces. the word count of a sender is the * total number of words sent by the sender. note that a sender may send more * than one message. return the sender with the largest word count. if there is * more than one sender with the largest word count, return the one with the * lexicographically largest name */ typedef struct { uint val; char *str; int cnt; } dict; uint rs_hash(char *str) { uint a = 63689, b = 378551, hash = 0; while (*str) { hash = hash * a + (*str++); a *= b; } return (hash & 0x7FFFFFFF); } int cmp(const void *a, const void *b) { dict aa = **(dict **)a; dict bb = **(dict **)b; if (aa.cnt == bb.cnt) return strcmp(aa.str, bb.str); return aa.cnt - bb.cnt; } char *largestWordCount(char **messages, int messages_size, char **senders, int senders_size) { int n = senders_size, *words = calloc(n, sizeof(int)); for (int i = 0; i < n; i++) { int len = strlen(messages[i]); if (!len) { words[i] = 0; continue; } words[i] = 1; for (int j = 0; j < len; j++) if (messages[i][j] == ' ') words[i]++; dict **hash = malloc(n * sizeof(dict *)); for (int i = 0; i < n; i++) { hash[i] = malloc(sizeof(dict)); hash[i]->cnt = 0; } int max = 0, pos = 0; dict **max_data = malloc(n * sizeof(dict *)); for (int i = 0; i < n; i++) { uint h = rs_hash(senders[i]); if (!hash[h % n]->cnt) { hash[h % n]->cnt = words[i]; int len = strlen(senders[i]); hash[h % n]->str = malloc((len + 1) * sizeof(char)); strcpy(hash[h % n]->str, senders[i]); hash[h % n]->val = h; if (hash[h % n]->cnt == max) { max_data[pos] = hash[h % n]; pos++; } if (hash[h % n]->cnt > max) { pos = 0; max = hash[h % n]->cnt; max_data[pos] = hash[h % n]; pos++; } } else if (hash[h % n]->val == h) { hash[h % n]->cnt += words[i]; if (hash[h % n]->cnt == max) { max_data[pos] = hash[h % n]; pos++; } if (hash[h % n]->cnt > max) { pos = 0; max = hash[h % n]->cnt; max_data[pos] = hash[h % n]; pos++; } } else { int k = (h + 1) % n; bool done = false; while (hash[k]->cnt) { if (hash[k]->val == h) { hash[k]->cnt += words[i]; if (hash[k]->cnt == max) { max_data[pos] = hash[k]; pos++; } if (hash[k]->cnt > max) { pos = 0; max = hash[k]->cnt; max_data[pos] = hash[k]; pos++; } done = true; break; } k = (k + 1) % n; } if (!done) { hash[k]->val = h; hash[k]->cnt = words[i]; int len = strlen(senders[i]); hash[k]->str = malloc((len + 1) * sizeof(char)); strcpy(hash[k]->str, senders[i]); if (hash[k]->cnt == max) { max_data[pos] = hash[k]; pos++; } if (hash[k]->cnt > max) { pos = 0; max = hash[k]->cnt; max_data[pos] = hash[k]; pos++; } } } } qsort(max_data, pos, sizeof(dict *), cmp); return max_data[pos - 1]->str; } } int main() { char m1[4][19] = {"Hello userTwooo", "Hi userThree", "Wonderful day Alice", "Nice day userThree"}; char s1[4][9] = {"Alice", "userTwo", "userThree", "Alice"}; char m2[2][31] = {"How is leetcode for everyone", "Leetcode is useful for practice"}; char s2[2][7] = {"Bob", "Charlie"}; printf("%s\n", largestWordCount(m1, 4, s1, 4)); // expect: Alice printf("%s\n", largestWordCount(m2, 2, s2, 2)); // expect: Charlie }