929. Unique Email Addresses - Explanation

Description

A 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 "alice@neetcode.io", "alice" is the local name, and "neetcode.io" 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, "alice.z@neetcode.io" and "alicez@neetcode.io" 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, "m.y+name@email.com" will be forwarded to "my@email.com".
It is possible to use both of these rules at the same time.

You are 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 = ["test.email+alex@neetcode.com","test.e.mail+bob.cathy@neetcode.com","testemail+david@nee.tcode.com"]

Output: 2

Explanation: "testemail@neetcode.com" and "testemail@nee.tcode.com" actually receive mails.

Example 2:

Input: emails = ["a@neetcode.com","b@neetcode.com","c@neetcode.com"]

Output: 3

Constraints:

1 <= emails.length <= 100
1 <= emails[i].length <= 100
emails[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.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Set - Used to store and count unique email addresses efficiently
String Manipulation - Splitting strings, replacing characters, and extracting substrings

1. Built-In Functions

Intuition

Each email consists of a local name and domain separated by @. For the local name, periods are ignored and everything after + is discarded. The domain remains unchanged. Two emails are the same if they resolve to the same address after applying these rules.

We can leverage built-in string functions to parse and normalize each e mail, then use a set to count unique addresses.

Algorithm

Initialize an empty set unique to store unique email addresses.
For each email e:
- Split by @ to get local and domain.
- Split local by + and take only the first part.
- Remove all periods from local.
- Combine the normalized local with domain and add to unique.
Return the size of unique.

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        unique = set()

        for e in emails:
            local, domain = e.split('@')
            local = local.split("+")[0]
            local = local.replace(".", "")
            unique.add((local, domain))
        return len(unique)

public class Solution {
    public int numUniqueEmails(String[] emails) {
        Set<String> unique = new HashSet<>();

        for (String e : emails) {
            String[] parts = e.split("@");
            String local = parts[0];
            String domain = parts[1];

            local = local.split("\\+")[0];
            local = local.replace(".", "");
            unique.add(local + "@" + domain);
        }
        return unique.size();
    }
}

class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> unique;

        for (string e : emails) {
            string local = e.substr(0, e.find('@'));
            local = local.substr(0, local.find('+'));
            local.erase(remove(local.begin(), local.end(), '.'), local.end());
            unique.insert(local + e.substr(e.find('@')));
        }
        return unique.size();
    }
};

class Solution {
    /**
     * @param {string[]} emails
     * @return {number}
     */
    numUniqueEmails(emails) {
        const unique = new Set();

        for (let e of emails) {
            let [local, domain] = e.split('@');
            local = local.split('+')[0];
            local = local.replace(/\./g, '');
            unique.add(`${local}@${domain}`);
        }
        return unique.size;
    }
}

public class Solution {
    public int NumUniqueEmails(string[] emails) {
        HashSet<string> unique = new HashSet<string>();

        foreach (string e in emails) {
            string[] parts = e.Split('@');
            string local = parts[0];
            string domain = parts[1];

            local = local.Split('+')[0];
            local = local.Replace(".", "");
            unique.Add(local + "@" + domain);
        }

        return unique.Count;
    }
}

func numUniqueEmails(emails []string) int {
    unique := make(map[string]bool)

    for _, e := range emails {
        parts := strings.Split(e, "@")
        local, domain := parts[0], parts[1]

        local = strings.Split(local, "+")[0]
        local = strings.ReplaceAll(local, ".", "")

        key := local + "@" + domain
        unique[key] = true
    }

    return len(unique)
}

class Solution {
    fun numUniqueEmails(emails: Array<String>): Int {
        val unique = HashSet<String>()

        for (e in emails) {
            val parts = e.split("@")
            var local = parts[0]
            val domain = parts[1]

            local = local.split("+")[0]
            local = local.replace(".", "")
            unique.add("$local@$domain")
        }
        return unique.size
    }
}

class Solution {
    func numUniqueEmails(_ emails: [String]) -> Int {
        var unique = Set<String>()

        for e in emails {
            let parts = e.split(separator: "@")
            var local = String(parts[0])
            let domain = String(parts[1])

            local = String(local.split(separator: "+")[0])
            local = local.replacingOccurrences(of: ".", with: "")
            unique.insert("\(local)@\(domain)")
        }
        return unique.count
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the number of strings in the array, and $m$ is the average length of these strings.

2. Iteration

Intuition

Instead of using built-in string functions, we can manually iterate through each character of the email. This gives us more control and can be slightly more efficient since we process each character exactly once.

Algorithm

Initialize an empty set unique to store unique email addresses.
For each email e:
- Initialize an empty string local and set index i = 0.
- While the current character is not @ or +:
  - If the character is not ., append it to local.
  - Increment i.
- Skip characters until we reach @.
- Extract domain as the substring after @.
- Add the normalized email (local + domain) to unique.
Return the size of unique.

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        unique = set()

        for e in emails:
            i, local = 0, ""
            while e[i] not in ["@", "+"]:
                if e[i] != ".":
                    local += e[i]
                i += 1

            while e[i] != "@":
                i += 1
            domain = e[i + 1:]
            unique.add((local, domain))
        return len(unique)

public class Solution {
    public int numUniqueEmails(String[] emails) {
        Set<String> unique = new HashSet<>();

        for (String e : emails) {
            int i = 0;
            StringBuilder local = new StringBuilder();
            while (i < e.length() && e.charAt(i) != '@' && e.charAt(i) != '+') {
                if (e.charAt(i) != '.') {
                    local.append(e.charAt(i));
                }
                i++;
            }

            while (i < e.length() && e.charAt(i) != '@') {
                i++;
            }
            String domain = e.substring(i + 1);
            unique.add(local.toString() + "@" + domain);
        }
        return unique.size();
    }
}

class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> unique;

        for (string e : emails) {
            int i = 0;
            string local = "";
            while (i < e.length() && e[i] != '@' && e[i] != '+') {
                if (e[i] != '.') {
                    local += e[i];
                }
                i++;
            }

            while (i < e.length() && e[i] != '@') {
                i++;
            }
            string domain = e.substr(i + 1);
            unique.insert(local + "@" + domain);
        }
        return unique.size();
    }
};

class Solution {
    /**
     * @param {string[]} emails
     * @return {number}
     */
    numUniqueEmails(emails) {
        const unique = new Set();

        for (let e of emails) {
            let i = 0,
                local = '';
            while (i < e.length && e[i] !== '@' && e[i] !== '+') {
                if (e[i] !== '.') {
                    local += e[i];
                }
                i++;
            }

            while (i < e.length && e[i] !== '@') {
                i++;
            }
            const domain = e.slice(i + 1);
            unique.add(`${local}@${domain}`);
        }
        return unique.size;
    }
}

public class Solution {
    public int NumUniqueEmails(string[] emails) {
        HashSet<string> unique = new HashSet<string>();

        foreach (string e in emails) {
            int i = 0;
            StringBuilder local = new StringBuilder();

            while (i < e.Length && e[i] != '@' && e[i] != '+') {
                if (e[i] != '.') {
                    local.Append(e[i]);
                }
                i++;
            }

            while (i < e.Length && e[i] != '@') {
                i++;
            }

            string domain = e.Substring(i + 1);
            unique.Add(local.ToString() + "@" + domain);
        }

        return unique.Count;
    }
}

func numUniqueEmails(emails []string) int {
    unique := make(map[string]bool)

    for _, e := range emails {
        i := 0
        local := ""

        for e[i] != '@' && e[i] != '+' {
            if e[i] != '.' {
                local += string(e[i])
            }
            i++
        }

        for e[i] != '@' {
            i++
        }
        domain := e[i+1:]

        key := local + "@" + domain
        unique[key] = true
    }

    return len(unique)
}

class Solution {
    fun numUniqueEmails(emails: Array<String>): Int {
        val unique = HashSet<String>()

        for (e in emails) {
            var i = 0
            val local = StringBuilder()
            while (i < e.length && e[i] != '@' && e[i] != '+') {
                if (e[i] != '.') {
                    local.append(e[i])
                }
                i++
            }

            while (i < e.length && e[i] != '@') {
                i++
            }
            val domain = e.substring(i + 1)
            unique.add("$local@$domain")
        }
        return unique.size
    }
}

class Solution {
    func numUniqueEmails(_ emails: [String]) -> Int {
        var unique = Set<String>()

        for e in emails {
            let chars = Array(e)
            var i = 0
            var local = ""

            while i < chars.count && chars[i] != "@" && chars[i] != "+" {
                if chars[i] != "." {
                    local.append(chars[i])
                }
                i += 1
            }

            while i < chars.count && chars[i] != "@" {
                i += 1
            }
            let domain = String(chars[(i + 1)...])
            unique.insert("\(local)@\(domain)")
        }
        return unique.count
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the number of strings in the array, and $m$ is the average length of these strings.

Common Pitfalls

Applying Local Name Rules to the Domain

A common mistake is applying the period-removal and plus-sign rules to the entire email address instead of just the local name. The domain portion (after the @ symbol) must remain unchanged. Periods in domain names like gmail.com are meaningful and should never be removed.

Incorrect Handling of the Plus Sign

Some solutions incorrectly remove only the + character itself rather than everything from + to the @. The rule states that everything after the first + in the local name should be ignored, not just the plus character. For example, in test+spam@gmail.com, the entire +spam portion must be discarded.