leetcode

0 // Group by first letter, 637ms

1 class Solution {

2 public:

3 long long distinctNames(vector<string> &ideas) {

4 array<unordered_set<string>, 26> um;

5 for (const auto &idea : ideas)

6 um[idea.front() - 'a'].insert(idea.substr(1));

7

8 long long res = 0ll;

9 for (int i = 0; i < 26; i++) {

10 for (int j = i + 1; j < 26; j++) {

11 long long c1 = 0ll, c2 = 0ll;

12 for (const auto &s : um[i])

13 c1 += !um[j].count(s);

14 for (const auto &s : um[j])

15 c2 += !um[i].count(s);

16 res += c1 * c2;

17 }

18 }

19

20 return res * 2;

21 }

22 };

23

24 // Group by suffix, 373ms

25 class Solution {

26 public:

27 long long distinctNames(vector<string> &ideas) {

28 unordered_map<string, bitset<32>> um;

29 unordered_map<bitset<32>, int> cnt;

30

31 for (const auto &idea : ideas)

32 um[idea.substr(1)].set(idea.front() - 'a');

33 for (const auto &[k, v] : um)

34 cnt[v]++;

35

36 long long res = 0ll;

37 for (auto it1 = cnt.begin(); it1 != cnt.end(); it1++) {

38 for (auto it2 = next(it1); it2 != cnt.end(); it2++) {

39 int same = (it1->first & it2->first).count();

40 res += (it2->first.count() - same) * (it1->first.count() - same) * it1->second * it2->second;

41 }

42 }

43

44 return res * 2;

45 }

46 };