Leetcode 2284: Sender With Largest Word Count
You are given two arrays: one containing a series of messages, and another with the names of the senders corresponding to each message. A message is a list of words separated by spaces. Your task is to determine which sender has sent the most words across all their messages. If there is a tie for the most words, return the sender with the lexicographically larger name.
Problem
Approach
Steps
Complexity
Input: You are provided with two arrays, messages and senders, both of length n. Each message corresponds to a sender in the same index.
Example: Input: messages = ["I love coding","How are you today?","Great to see you here!"], senders = ["Bob","Charlie","Bob"]
Constraints:
• 1 <= n <= 10^4
• 1 <= messages[i].length <= 100
• 1 <= senders[i].length <= 10
• messages[i] consists of uppercase and lowercase English letters and spaces.
• Each message has no leading or trailing spaces.
• senders[i] consists of uppercase and lowercase English letters only.
Output: Return the sender who sent the most words across all their messages. If there is a tie, return the sender with the lexicographically larger name.
Example: Output: "Bob"
Constraints:
Goal: The goal is to identify the sender with the largest word count across all their messages. If multiple senders share the maximum word count, return the one with the lexicographically larger name.
Steps:
• Iterate through the list of senders and messages.
• Count the number of words in each message.
• Maintain a record of total word counts for each sender.
• At the end of the iteration, identify the sender with the highest word count. If there's a tie, return the lexicographically larger name.
Goal: The input is guaranteed to have at least one message and sender. All messages and senders are within the given constraints.
Steps:
Assumptions:
• Each sender sends at least one message.
• The word count can be calculated by splitting the message string by spaces.
• Input: Input: messages = ["I love coding","How are you today?","Great to see you here!"], senders = ["Bob","Charlie","Bob"]
• Explanation: Here, Bob sends 2 words in the first message and 5 words in the last message, for a total of 7 words. Charlie sends 4 words, so Bob is the sender with the largest word count.
• Input: Input: messages = ["Coding is fun","What are you doing?"], senders = ["Alice","Bob"]
• Explanation: Alice sends 3 words in the first message, while Bob sends 4 words. Bob, having sent more words, is returned.
Approach: To solve this problem efficiently, we'll iterate through the arrays to calculate the total word count for each sender. Then, we'll compare the word counts and return the sender with the highest count, resolving ties based on lexicographical order.
Observations:
• The word count for each message can be easily determined by counting spaces and adding one.
• We need to handle ties by lexicographical order.
• We can use a hashmap to track the total word count for each sender.
Steps:
• Step 1: Initialize an empty hashmap to store word counts for each sender.
• Step 2: Iterate through each message, count the words, and update the sender's total word count in the hashmap.
• Step 3: After processing all messages, iterate through the hashmap to find the sender with the highest word count, resolving ties based on lexicographical order.
Empty Inputs:
• Messages and senders arrays cannot be empty.
Large Inputs:
• The algorithm should efficiently handle up to 10^4 messages.
Special Values:
• Messages with varying spaces between words and senders with the same number of words.
Constraints:
• Consider the lexicographical order in case of ties.
string largestWordCount(vector<string>& messages, vector<string>& senders) {
unordered_map<string, int> cnt;
string res;
int max_cnt = 0;
for(int i = 0; i < senders.size(); i++) {
int words = count(begin(messages[i]), end(messages[i]), ' ') + 1;
int cur = cnt[senders[i]] += words;
if((cur > max_cnt) || (cur == max_cnt && senders[i] > res)) {
res = senders[i];
max_cnt = cur;
}
}
return res;
}
1 : Function Declaration
string largestWordCount(vector<string>& messages, vector<string>& senders) {
The function `largestWordCount` is defined to return a string (the sender with the most words). It takes two vectors of strings: `messages` (the content of messages) and `senders` (the names of the senders).
2 : Initialize Count Map
unordered_map<string, int> cnt;
An unordered map `cnt` is initialized, where the keys are sender names and the values are the total word counts for each sender's messages.
3 : Initialize Result Variables
string res;
A string `res` is declared to store the sender with the maximum word count.
4 : Initialize Maximum Count
int max_cnt = 0;
An integer `max_cnt` is initialized to track the highest word count encountered during iteration.
5 : Iterate Over Senders
for(int i = 0; i < senders.size(); i++) {
A `for` loop is started to iterate over each sender in the `senders` vector and corresponding messages in `messages`.
6 : Count Words in Message
int words = count(begin(messages[i]), end(messages[i]), ' ') + 1;
The number of words in the current message (`messages[i]`) is calculated by counting spaces and adding 1 (to account for the last word).
7 : Update Word Count for Sender
int cur = cnt[senders[i]] += words;
The word count for the current sender is updated by adding the number of words in their message.
8 : Check for Maximum Word Count
if((cur > max_cnt) || (cur == max_cnt && senders[i] > res)) {
If the current sender's word count exceeds `max_cnt` or equals it but has a lexicographically larger name than the current result (`res`), the sender becomes the new candidate.
9 : Update Result and Max Count
res = senders[i];
If the condition is satisfied, the sender with the maximum word count (or the lexicographically larger name) is saved as `res`.
10 :
max_cnt = cur;
The variable `max_cnt` is updated to the current word count (`cur`) of the sender.
11 : Return the Result
return res;
The function returns the sender with the maximum word count (or the lexicographically largest sender name in case of a tie).
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) where n is the number of messages because we process each message and sender once.
Best Case: O(n)
Worst Case: O(n)
Description: We store the word count for each sender, so the space complexity is O(n) where n is the number of unique senders.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus