# Leetcode 2306. Naming a Company

## Problem
[Link](https://leetcode.com/problems/naming-a-company/)

## Thinking
Group words by **first letter**.

Obviously, two words in the same group (i.e. same first letter) cannot form a valid pair.

For convenience, let's store each word by their suffix.

Consider two different groups, say group 'b' and group 'c'.
Let `s1` be a suffix in group 'b'.

### Think
> **If `s1` is in group 'c', then `s1` cannot form valid pair with any suffix in group 'c'.**

So if `s1` is not in group 'c', then it can form with any word in group 'c' except for those who have also appeared in group 'b'.

For example:

| 'b' | 'c' |
| -------- | -------- |
| out | out |
| anana | oconut |
| affalo | at |

"anana" can form pairs with "oconut" and "at".
"affalo" can form pairs with "oconut" and "at".
"oconut" can form pairs with "anana" and "afflo".
"at" can form pairs with "anana" and "afflo".

Total of 4 pairs form.
In fact,
$$
4 = \text{#(words in group 'b' that doesn't appear in group 'c')} *\text{#(words in group 'c' that doesn't appear in group 'b')}
$$

So the problem boils down to
**How to efficiently find the two terms (let's call them `c1`, `c2`) in the above equation?**

A simple approach is
for each word in group 'b'
check by `map` to see if it is in group 'c', after which we would get `c1`,
and vice versa for computing `c2`.

ans = 0
for char1 = 'a' to 'z':
    for char2 = char1 + 1 to 'z':
        c1, c2 = 0, 0
        for each suffix s1 in count[char1]:
            if s1 not in count[char2]: c1++
        for each suffix s2 in count[char2]:
            if s2 not in count[char1]: c2++
        ans += c1*c2
return ans

## Improvement (Tricky!)
Using map would be somehow slow, and we need a `map` for each letter.
Also, computing `c1` and `c2` for each pair of groups requires enumerating each word in each group.

In fact, we can use `array` to solve the problem more efficiently.

The key idea is that
> **If two groups share a suffix, then `c1` must decrease by 1 and `c2` must also decrease by 1.**

Let `invalid[i][j]` be the number of **shared** suffix when considering group `i` and group `j`.

We use a map `group` whose
- key = suffix
- value = integer, where the i-th bit represents whether the suffix is in i-th group

The algorithm works as follows

count = [26]int{}
group = map[string]int
invalid = [26][26]int{}

# i, j: groups that we are considering
for each word in words:
    j = word[0]
    count[j]++
    
    mask = suffix[word[1:]]
    for i = 0 to 25:
        if i-th bit of mask is 1: # two groups share the same suffix
            invalid[i][j]++
            invalid[j][i]++
    
    turn (word[0]-'a')-th bit of group[word[1:]] to 1
    

ans = 0
for i = 0 to 25:
    for j = i+1 to 25:
        c1 = count[i] - invalid[i][j]
        c2 = count[j] - invalid[j][i]
        ans += c1*c2

###### tags: `Leetcode`