Unique Email Addresses
EasyPrompt
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 '+'.
- For example, in
"[email protected]","alice"is the local name, and"leetcode.com"is the domain name.
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.
- For example,
"[email protected]"and"[email protected]"forward to the same email address.
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.
- For example,
"[email protected]"will be forwarded to"[email protected]".
It is possible to use both of these rules at the same time.
Given an array of strings emails where we send one email to each emails[i], return the number of different addresses that actually receive mails.
Example 1:
Input: emails = ["[email protected]","[email protected]","[email protected]"]
Output: 2
Explanation: "[email protected]" and "[email protected]" actually receive mails.Example 2:
Input: emails = ["[email protected]","[email protected]","[email protected]"]
Output: 3
Constraints:
1 <= emails.length <= 1001 <= emails[i].length <= 100emails[i]consist of lowercase English letters,'+','.'and'@'.- Each
emails[i]contains exactly one'@'character. - All local and domain names are non-empty.
- Local names do not start with a
'+'character. - Domain names end with the
".com"suffix. - Domain names must contain at least one character before
".com"suffix.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves using standard string manipulation functions like split(), substring(), and replaceAll() to process each email address. We first separate the local and domain names, then apply the specified rules to the local name, and finally reconstruct the canonical email address. A HashSet is used to store the unique canonical addresses to count them.
Algorithm
- Initialize an empty
HashSet<String>calleduniqueEmails. - For each
emailstring in the inputemailsarray:- Split the
emailintolocalanddomainparts using'@'as the delimiter. - Find the index of
'+'in thelocalpart. If it exists, updatelocalto be the substring before the'+'. - Remove all
'.'characters from thelocalpart. - Form the canonical email by concatenating the processed
localpart,'@', and thedomainpart. - Add the canonical email to the
uniqueEmailsset.
- Split the
- Return the size of
uniqueEmails.
Walkthrough
The core idea is to iterate through each email in the input array. For each email, we first locate the '@' symbol to separate the local part from the domain part. The split("@") method is a convenient way to do this. Next, we process the local part. We need to handle the '+' rule first. We find the index of the first '+' and take the substring before it. If no '+' is present, we use the entire local part. Then, we apply the '.' rule to this modified local part. The replaceAll("\\.", "") method can be used to remove all dots. After cleaning the local part, we concatenate it with the '@' symbol and the original domain part to form the final, canonical email address. This canonical address is then added to a HashSet. The HashSet automatically handles duplicates, so we don't need to check for existence before adding. After processing all emails, the size of the HashSet gives us the number of unique email addresses that will receive mail.
import java.util.HashSet;import java.util.Set; class Solution { public int numUniqueEmails(String[] emails) { Set<String> uniqueEmails = new HashSet<>(); for (String email : emails) { String[] parts = email.split("@"); String local = parts[0]; String domain = parts[1]; // Handle '+' rule int plusIndex = local.indexOf('+'); if (plusIndex != -1) { local = local.substring(0, plusIndex); } // Handle '.' rule local = local.replaceAll("\\.", ""); String canonicalEmail = local + "@" + domain; uniqueEmails.add(canonicalEmail); } return uniqueEmails.size(); }}Complexity
Time
O(N * L), where N is the number of emails and L is the maximum length of an email. For each email, `split`, `indexOf`, `substring`, and `replaceAll` all take time proportional to the length of the string, L. Adding a string of length L to a hash set also takes O(L).
Space
O(N * L), where N is the number of emails and L is the maximum length of an email. In the worst case, all emails are unique, and we store N canonical emails of average length L in the `HashSet`. Also, intermediate strings are created during manipulation, contributing O(L) space per email.
Trade-offs
Pros
Simple and easy to understand as it directly maps the problem rules to high-level functions.
Code is concise and readable.
Cons
Less efficient due to the creation of multiple intermediate string objects for each email (from
split,substring,replaceAll).This can lead to higher memory usage and slower performance compared to a manual parsing approach.
Solutions
Solution
class Solution {public int numUniqueEmails(String[] emails) { Set<String> s = new HashSet<>(); for (String email : emails) { String[] t = email.split("@"); String local = t[0].replace(".", ""); String domain = t[1]; int i = local.indexOf('+'); if (i != -1) { local = local.substring(0, i); } s.add(local + "@" + domain); } return s.size(); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.