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.
This is a more optimized approach that avoids creating multiple intermediate strings. We iterate through each email character by character and build the canonical email address using a StringBuilder. This reduces memory allocations and can be faster in practice.
Algorithm
- Initialize an empty
HashSet<String>calleduniqueEmails. - For each
emailstring in the inputemailsarray:- Find the index of
'@', let's call itatIndex. - Get the domain part by taking the substring from
atIndexto the end. - Initialize an empty
StringBuildercalledlocalPartBuilder. - Iterate through the local part of the email (from index
0toatIndex - 1):- Get the character
cat the current index. - If
cis'+', stop processing the local part and break the loop. - If
cis not'.', append it tolocalPartBuilder.
- Get the character
- Append the domain part to the
localPartBuilder. - Add the final string from
localPartBuilder.toString()to theuniqueEmailsset.
- Find the index of
- Return the size of
uniqueEmails.
Walkthrough
Instead of relying on string splitting and replacement functions, this method processes each email in a single pass. We iterate through each email and build the canonical version in a StringBuilder. We first find the '@' symbol to separate the local and domain parts. We then iterate through the characters of the local part. If we see a '.', we simply ignore it. If we see a '+', we stop processing the local part entirely. All other characters from the local part are appended to our StringBuilder. Once the local part is processed, we append the domain part (from '@' onwards) to the StringBuilder. The resulting string from the StringBuilder is the canonical email, which we add to a HashSet. Finally, the size of the set is returned. This method is more efficient as it scans the string once and minimizes object creation.
import java.util.HashSet;import java.util.Set; class Solution { public int numUniqueEmails(String[] emails) { Set<String> uniqueEmails = new HashSet<>(); for (String email : emails) { StringBuilder canonicalEmail = new StringBuilder(); int atIndex = email.indexOf('@'); String domain = email.substring(atIndex); for (int i = 0; i < atIndex; i++) { char c = email.charAt(i); if (c == '+') { break; } if (c != '.') { canonicalEmail.append(c); } } canonicalEmail.append(domain); uniqueEmails.add(canonicalEmail.toString()); } return uniqueEmails.size(); }}Complexity
Time
O(N * L), where N is the number of emails and L is the maximum length of an email. We iterate through each email once. The operations inside the loop are efficient. The overall complexity remains the same as the first approach asymptotically, but with a better constant factor.
Space
O(N * L). The space is dominated by the `HashSet` storing the canonical emails. The `StringBuilder` uses O(L) auxiliary space for each email.
Trade-offs
Pros
More efficient in terms of both time and memory in practice.
Avoids creating unnecessary intermediate string objects, reducing garbage collection overhead.
Processes each email's local part in a single pass.
Cons
The code can be slightly more complex to write and read compared to the high-level string function 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(); }}const numUniqueEmails2 = function ( emails ) { const emailFilter = function ( str ) { let index = str . search ( /@/ ); let s = str . substring ( 0 , index ); let s2 = str . substring ( index + 1 , str . length ); let res = '' ; for ( let i = 0 ; i < s . length ; i ++ ) { if ( s [ i ] === ' + ' ) break ; if ( s [ i ] === ' . ' ) continue ; res = res + s [ i ]; } return res + s2 ; }; let arr = []; for ( let i = 0 ; i < emails . length ; i ++ ) { let t = emailFilter ( emails [ i ]); if ( arr . indexOf ( t ) === - 1 ) { arr . push ( t ); } } return arr . length ; }; const numUniqueEmails = function ( emails ) { let arr = emails . map ( str => { let index = str . search ( /@/ ); let s = str . substring ( 0 , index ); let s2 = str . substring ( index + 1 , str . length ); let res = '' ; for ( let i = 0 ; i < s . length ; i ++ ) { if ( s [ i ] === ' + ' ) break ; if ( s [ i ] === ' . ' ) continue ; res = res + s [ i ]; } return res + s2 ; }); let set = new Set ( arr ); return set . size ; };class Solution {public: int numUniqueEmails(vector<string> &emails) { unordered_set<string> s; for (auto &email : emails) { int i = email.find('@'); string local = email.substr(0, i); string domain = email.substr(i + 1); i = local.find('+', 0); if (~i) local = local.substr(0, i); while (~(i = local.find('.', 0))) local.erase(local.begin() + i); s.insert(local + "@" + domain); } return s.size(); }};class Solution: def numUniqueEmails(self, emails: List[str]) -> int: s = set() for email in emails: local, domain = email . split('@') local = local . replace('.', '') if (i: = local . find('+')) != - 1: local = local[: i] s . add(local + '@' + domain) return len(s)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.