Mail Rules

Easy
0/40
3 upvotes
Asked in company
VMware Inc

Problem statement

Every valid email consists of a local name and a domain name, separated by the '@' sign. Besides lowercase letters, the email may contain one or more '.' or '+'.


If you add periods '.' between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. Note that this rule does not apply to domain names.


If you add a plus '+' in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered. Note that this rule does not apply to domain names.


It is possible to use both of these rules at the same time.


Given an array of 'N' strings 'emails' where we send one email to each emails[i], return the number of different addresses that actually receive mails.


For Example : 
Let 'emails' = ["test.email+alex@ninjas.com", "test.e.mail+bob.case@ninjas.com", "testemail@ninjas.com"].
We need to find the number of unique email addresses after applying the rules.

The first email "test.email+alex@ninjas.com":
The local name is "test.email+alex" and the domain name is "ninjas.com".
Applying the rules to the local name:
Remove '.' -> "testemail+alex"
Ignore everything after '+' -> "testemail"
The processed email address is "testemail@ninjas.com".

The second email "test.e.mail+bob.case@ninjas.com":
The local name is "test.e.mail+bob.case" and the domain name is "ninjas.com".
Applying the rules to the local name:
Remove '.' -> "testemail+bob.case"
Ignore everything after '+' -> "testemail"
The processed email address is "testemail@ninjas.com".

The third email "testemail@ninjas.com":
The local name is "testemail" and the domain name is "ninjas.com".
No '.' or '+' in the local name.
The processed email address is "testemail@ninjas.com".

The unique processed email addresses are {"testemail@ninjas.com"}.
Therefore, the number of different addresses that actually receive mails is 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer 'N' denoting the length of the array.
The second line contains the array of strings 'emails'.
Output Format : 
Return a single integer, the number of different addresses that actually receive mails.
Note : 
You don’t need to print anything. Just implement the given function.
Constraints : 
1 <= 'N' <= 100
1 <= length of emails[i] <= 100
emails[i] consists of lowercase letters, '.', '+', and '@'.
Each emails[i] contains exactly one '@' character.
The local and domain names are non-empty.

Time Limit: 1 sec
Sample Input 1 :
3
a@ninjas.com b@ninjas.com c@ninjas.com
Sample Output 1 :
3
Explanation of sample input 1 :
The given emails are ["a@ninjas.com","b@ninjas.com","c@ninjas.com"].
The first email "a@ninjas.com": local name "a", domain name "ninjas.com". Processed: "a@ninjas.com".
The second email "b@ninjas.com": local name "b", domain name "ninjas.com". Processed: "b@ninjas.com".
The third email "c@ninjas.com": local name "c", domain name "ninjas.com". Processed: "c@ninjas.com".
All three processed emails are unique: {"a@ninjas.com", "b@ninjas.com", "c@ninjas.com"}.
Thus, the answer is 3.
Sample Input 2 :
3
test.email+alex@ninjas.com test.email.goo+ciao@ninjas.com testemail@ninjas.com
Sample Output 2 :
2
Hint

How can you efficiently keep track of the unique email addresses after processing?

Approaches (1)
Set

Approach:

  • Initialize a set data structure to store the unique processed email addresses.
  • Iterate through each email string in the input array 'emails'.
  • For each email string:
    • Find the index of the '@' symbol to separate the local name and the domain name.
    • Process the local name according to the rules:
      • Iterate through the characters of the local name.
      • If a '+' character is encountered, stop processing the local name (ignore the rest of the characters).
      • If a '.' character is encountered, ignore it (do not include it in the processed local name).
      • Append all other characters to a new string representing the processed local name.
    • Construct the full processed email address by concatenating the processed local name, '@', and the original domain name.
    • Add this processed email address to the set. The set automatically handles uniqueness.
  • After processing all email strings, the size of the set will be the number of different addresses that actually receive mails.
  • Return the size of the set.

Algorithm:

  • Initialize an empty set called 'unique_emails'.
  • For each string 'email' in the input array 'emails':
    • Find the index of '@' in 'email'. Let this be 'at_index'.
    • Extract the local name: 'local_name' = 'email' from index 0 up to 'at_index' (exclusive).
    • Extract the domain name: 'domain_name' = 'email' from index 'at_index' + 1 to the end.
    • Initialize an empty string called 'processed_local_name'.
    • For each character 'char' in 'local_name':
      • If 'char' is '+':
        • Break the inner loop (stop processing local name).
      • If 'char' is not '.':
        • Append 'char' to 'processed_local_name'.
    • Construct the final processed email: 'processed_email' = 'processed_local_name' + '@' + 'domain_name'.
    • Add 'processed_email' to the set 'unique_emails'.
  • Return the size of the set 'unique_emails'.
Time Complexity

O(N * M), where 'N' is the number of emails in the input array 'emails' and 'M' is the maximum length of an email string.

We iterate through each of the 'N' email strings. For each email, we iterate through its characters up to the '@' symbol to process the local name. In the worst case, processing an email of length 'M' takes O(M) time. Adding to a set on average takes time proportional to the length of the string being added, which is at most O(M). Thus, the overall time complexity is of the order O(N * M).

Space Complexity

O(N * M), where 'N' is the number of emails in the input array 'emails' and 'M' is the maximum length of an email string.

In the worst case, all processed email addresses are unique and are stored in the set. The set can store up to 'N' strings, and each processed string can have a length up to 'M' (in the case where the local name contains no '.' or '+'). Thus, the overall space complexity is of the order O(N * M).

Code Solution
(100% EXP penalty)
Mail Rules
Full screen
Console