2306. Naming a Company Hard

1/**
2 * [2306] Naming a Company
3 *
4 * You are given an array of strings ideas that represents a list of names to be used in the process of naming a company. The process of naming a company is as follows:
5 * <ol>
6 * Choose 2 distinct names from ideas, call them ideaA and ideaB.
7 * Swap the first letters of ideaA and ideaB with each other.
8 * If both of the new names are not found in the original ideas, then the name ideaA ideaB (the concatenation of ideaA and ideaB, separated by a space) is a valid company name.
9 * Otherwise, it is not a valid name.
10 * </ol>
11 * Return the number of distinct valid names for the company.
12 *  
13 * Example 1:
14 *
15 * Input: ideas = ["coffee","donuts","time","toffee"]
16 * Output: 6
17 * Explanation: The following selections are valid:
18 * - ("coffee", "donuts"): The company name created is "doffee conuts".
19 * - ("donuts", "coffee"): The company name created is "conuts doffee".
20 * - ("donuts", "time"): The company name created is "tonuts dime".
21 * - ("donuts", "toffee"): The company name created is "tonuts doffee".
22 * - ("time", "donuts"): The company name created is "dime tonuts".
23 * - ("toffee", "donuts"): The company name created is "doffee tonuts".
24 * Therefore, there are a total of 6 distinct company names.
25 * The following are some examples of invalid selections:
26 * - ("coffee", "time"): The name "toffee" formed after swapping already exists in the original array.
27 * - ("time", "toffee"): Both names are still the same after swapping and exist in the original array.
28 * - ("coffee", "toffee"): Both names formed after swapping already exist in the original array.
29 *
30 * Example 2:
31 *
32 * Input: ideas = ["lack","back"]
33 * Output: 0
34 * Explanation: There are no valid selections. Therefore, 0 is returned.
35 *
36 *  
37 * Constraints:
38 *
39 * 2 <= ideas.length <= 5 * 10^4
40 * 1 <= ideas[i].length <= 10
41 * ideas[i] consists of lowercase English letters.
42 * All the strings in ideas are unique.
43 *
44 */
45pub struct Solution {}
46use std::collections::HashSet;
47
48// problem: https://leetcode.com/problems/naming-a-company/
49// discuss: https://leetcode.com/problems/naming-a-company/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn distinct_names(ideas: Vec<String>) -> i64 {
55        let mut names: Vec<HashSet<&str>> = vec![HashSet::new(); 26];
56
57        for i in ideas.iter() {
58            names[i.chars().next().unwrap() as usize - 'a' as usize].insert(&i[1..]);
59        }
60
61        let mut result = 0;
62        for x in 0..26 {
63            for y in x + 1..26 {
64                if names[x].is_empty() || names[y].is_empty() {
65                    continue;
66                }
67                let c1 = &names[x];
68                let c2 = &names[y];
69                result += 2 * (c1 - c2).len() * (c2 - c1).len();
70            }
71        }
72        result as i64
73    }
74}
75
76// submission codes end
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_2306() {
84        assert_eq!(
85            Solution::distinct_names(vec![
86                "coffee".to_owned(),
87                "donuts".to_owned(),
88                "time".to_owned(),
89                "toffee".to_owned()
90            ]),
91            6
92        );
93    }
94}
95