Skip to content

2306. Naming a Company 👍

  • Time: $O(n) + O(26^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  long long distinctNames(vector<string>& ideas) {
    long ans = 0;
    // suffixes[i] := the set of strings omitting the first letter, where the
    // first letter is ('a' + i)
    vector<unordered_set<string>> suffixes(26);

    for (const string& idea : ideas)
      suffixes[idea[0] - 'a'].insert(idea.substr(1));

    for (int i = 0; i < 25; ++i)
      for (int j = i + 1; j < 26; ++j) {
        int count = 0;
        for (const string& suffix : suffixes[i])
          if (suffixes[j].contains(suffix))
            ++count;
        ans += 2 * (suffixes[i].size() - count) * (suffixes[j].size() - count);
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public long distinctNames(String[] ideas) {
    long ans = 0;
    // suffixes[i] := the set of strings omitting the first letter, where the first letter is
    // ('a' + i)
    Set<String>[] suffixes = new Set[26];

    for (int i = 0; i < 26; ++i)
      suffixes[i] = new HashSet<>();

    for (final String idea : ideas)
      suffixes[idea.charAt(0) - 'a'].add(idea.substring(1));

    for (int i = 0; i < 25; ++i)
      for (int j = i + 1; j < 26; ++j) {
        int count = 0;
        for (final String suffix : suffixes[i])
          if (suffixes[j].contains(suffix))
            ++count;
        ans += 2 * (suffixes[i].size() - count) * (suffixes[j].size() - count);
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def distinctNames(self, ideas: list[str]) -> int:
    ans = 0
    # suffixes[i] := the set of strings omitting the first letter, where the
    # first letter is ('a' + i)
    suffixes = [set() for _ in range(26)]

    for idea in ideas:
      suffixes[ord(idea[0]) - ord('a')].add(idea[1:])

    for i in range(25):
      for j in range(i + 1, 26):
        count = len(suffixes[i] & suffixes[j])
        ans += 2 * (len(suffixes[i]) - count) * (len(suffixes[j]) - count)

    return ans