Sender With Largest Word Count

#956 Most AskedMedium

Sender With Largest Word Count #956 Most Asked

Medium

29 views

Topics:

ArraysStrings

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 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.

Note:

Uppercase letters come before lowercase letters in lexicographical order.
"Alice" and "alice" are distinct.

Example 1:

Input: messages = ["Hello userTwooo","Hi userThree","Wonderful day Alice","Nice day userThree"], senders = ["Alice","userTwo","userThree","Alice"]
Output: "Alice"
Explanation: Alice sends a total of 2 + 3 = 5 words.
userTwo sends a total of 2 words.
userThree sends a total of 3 words.
Since Alice has the largest word count, we return "Alice".

Example 2:

Input: messages = ["How is leetcode for everyone","Leetcode is useful for practice"], senders = ["Bob","Charlie"]
Output: "Charlie"
Explanation: Bob sends a total of 5 words.
Charlie sends a total of 5 words.
Since there is a tie for the largest word count, we return the sender with the lexicographically larger name, Charlie.

Constraints:

n == messages.length == senders.length
1 <= n <= 10⁴
1 <= messages[i].length <= 100
1 <= senders[i].length <= 10
messages[i] consists of uppercase and lowercase English letters and ' '.
All the words in messages[i] are separated by a single space.
messages[i] does not have leading or trailing spaces.
senders[i] consists of uppercase and lowercase English letters only.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can a sender have an empty message? If so, what should be the word count for that sender?
Are the senders and messages arrays guaranteed to be the same length?
What should I return if there is a tie for the largest word count? Should I return the sender that appears first lexicographically, or is there another tie-breaking rule?
Can the senders and messages contain non-alphanumeric characters or special symbols? Should I account for punctuation when splitting the messages into words?
Can senders or messages be null or empty strings? If so, how should I handle those cases?

Brute Force Solution

Approach

The brute force approach to this problem involves checking every sender and counting the words in each of their messages. We then compare the word counts of all the senders to find the largest. If multiple senders have the same largest count, we pick the one that comes latest in dictionary order.

Here's how the algorithm would work step-by-step:

For each sender, take their messages one by one.
For each message, count how many words it contains.
Add the number of words in that message to a running total for that sender.
Once you have processed all the messages for a sender, you have their total word count.
Repeat this process for every sender, storing their total word counts.
Now, compare all the total word counts to find the largest one.
If there is only one sender with the largest word count, that's your answer.
If multiple senders have the same largest word count, compare their names in alphabetical order and choose the last one.

Code Implementation

def sender_with_largest_word_count(messages, senders):
    sender_word_counts = {}

    for i in range(len(senders)):
        sender = senders[i]
        message = messages[i]

        # If sender not in dict, init count
        if sender not in sender_word_counts:

            sender_word_counts[sender] = 0

        words = message.split()
        sender_word_counts[sender] += len(words)

    largest_word_count = 0
    sender_with_largest_word_count = ''

    for sender, word_count in sender_word_counts.items():
        # Find largest word count
        if word_count > largest_word_count:

            largest_word_count = word_count
            sender_with_largest_word_count = sender
        elif word_count == largest_word_count:

            # If counts are same, lexicographical order matters
            if sender > sender_with_largest_word_count:

                sender_with_largest_word_count = sender

    return sender_with_largest_word_count

Big(O) Analysis

Time Complexity

O(m + n*k + s*log(s)) – Let m be the length of the senders array, n be the length of the messages array, k be the average length of the messages (number of words), and s be the number of unique senders. The first loop iterates through the senders array and its associated messages to calculate the word count for each sender, which takes O(n*k) time because we potentially iterate through all messages and count words in each message. Adding the words to the map of senders is O(m) since we iterate through the senders array once. Finally, identifying the sender with the largest word count and resolving ties using the dictionary order might require sorting the unique senders in the worst case if they all have the same word count, taking O(s*log(s)) time. Thus, the dominant terms are O(m + n*k + s*log(s)). In scenarios where m is relatively small compared to the other terms, we can simplify it to O(n*k + s*log(s)), but since the problem statement doesn't provide any assumptions we keep the original.

Space Complexity

O(N) – The algorithm stores the total word counts for each sender. In the worst case, each message could be from a different sender. If there are N messages, there could be up to N unique senders, requiring us to store N word counts. Therefore, the auxiliary space used by the algorithm scales linearly with the number of messages (N), leading to a space complexity of O(N).

Optimal Solution

Approach

The goal is to figure out which person sent the most words in their messages. We can do this efficiently by counting the words in each message and keeping track of who sent it, then comparing the counts to find the person with the highest total.

Here's how the algorithm would work step-by-step:

Create a way to remember how many words each person has sent. We'll update this as we go.
Go through each message one by one.
For each message, split it up into individual words and count how many there are.
Find out who sent the message.
Add the word count from the message to the person's total word count that we're remembering.
Once we've gone through all the messages, find the person with the highest total word count.
If multiple people have the same highest count, pick the one that comes last alphabetically.
The person you find is the answer.

Code Implementation

def sender_with_largest_word_count(messages, senders):
    word_counts_by_sender = {}

    for i in range(len(messages)):
        message = messages[i]
        sender = senders[i]
        words = message.split()
        word_count = len(words)

        # Store/update each sender's total word count.
        if sender not in word_counts_by_sender:
            word_counts_by_sender[sender] = word_count

        else:
            word_counts_by_sender[sender] += word_count

    largest_word_count = 0
    sender_with_largest_word_count = ""

    # Find the sender with the most words and pick the largest alphabetically
    for sender, total_word_count in word_counts_by_sender.items():
        if total_word_count > largest_word_count:
            largest_word_count = total_word_count
            sender_with_largest_word_count = sender

        elif total_word_count == largest_word_count:
            # Ensuring lexicographical order in case of a tie
            sender_with_largest_word_count = max(sender_with_largest_word_count, sender)

    return sender_with_largest_word_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the 'messages' array of size n once. Within the loop, the most expensive operation is splitting each message into words, which takes time proportional to the length of the message. However, even if we assume the worst case where the average message length is constant, splitting each message still takes constant time per message and the split is part of the singular 'for' loop. Updating the word counts for each sender takes constant time. Therefore, the dominant factor is the single loop iterating through n messages, making the time complexity O(n).

Space Complexity

O(N) – The solution uses a hash map (or similar data structure) to store the word count for each sender. In the worst case, each message could be from a different sender, resulting in N entries in the hash map, where N is the number of messages. Therefore, the auxiliary space used by the hash map grows linearly with the number of messages. The extra space used is proportional to the number of senders which is bounded by the number of messages which results in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty messages array	Return an empty string if the messages array is null or empty to avoid NullPointerException or incorrect results.
Null or empty senders array	Return an empty string if the senders array is null or empty to avoid NullPointerException or incorrect results.
Messages and senders arrays of different lengths	Throw an IllegalArgumentException or return an error string, as it indicates invalid input.
Empty message strings	Treat empty messages as having a word count of 0 and proceed with the comparison.
Messages with leading/trailing spaces	Trim leading/trailing spaces from each message string before counting words to ensure accurate results.
Messages with multiple spaces between words	Split the message string using a regular expression that handles multiple spaces to get the correct word count.
Multiple senders with the same maximum word count	Use the sender with the lexicographically largest name among those with the maximum count.
Very long messages that might cause integer overflow when counting words.	Although unlikely given reasonable input, consider using a data type with a larger range for word count (e.g., long) if extremely long messages are expected, or handle potential overflow exceptions.

Null or empty messages array

How to Handle:

Return an empty string if the messages array is null or empty to avoid NullPointerException or incorrect results.

Null or empty senders array

How to Handle:

Return an empty string if the senders array is null or empty to avoid NullPointerException or incorrect results.

Messages and senders arrays of different lengths

How to Handle:

Throw an IllegalArgumentException or return an error string, as it indicates invalid input.

Empty message strings

How to Handle:

Treat empty messages as having a word count of 0 and proceed with the comparison.

Messages with leading/trailing spaces

How to Handle:

Trim leading/trailing spaces from each message string before counting words to ensure accurate results.

Messages with multiple spaces between words

How to Handle:

Split the message string using a regular expression that handles multiple spaces to get the correct word count.

Multiple senders with the same maximum word count

How to Handle:

Use the sender with the lexicographically largest name among those with the maximum count.

Very long messages that might cause integer overflow when counting words.

How to Handle:

Although unlikely given reasonable input, consider using a data type with a larger range for word count (e.g., long) if extremely long messages are expected, or handle potential overflow exceptions.