# Naming a Company
**Difficulty:** HARD
[External](https://leetcode.com/problems/naming-a-company)
Canonical: https://scaleengineer.com/dsa/problems/naming-a-company
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table, String
---
## Problem
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:

1. Choose 2 **distinct** names from `ideas`, call them `ideaA` and `ideaB`.
2. Swap the first letters of `ideaA` and `ideaB` with each other.
3. 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.
4. Otherwise, it is not a valid name.

Return _the number of **distinct** valid names for the company_.

**Example 1:**

**Input:** ideas = ["coffee","donuts","time","toffee"]
**Output:** 6
**Explanation:** The following selections are valid:
- ("coffee", "donuts"): The company name created is "doffee conuts".
- ("donuts", "coffee"): The company name created is "conuts doffee".
- ("donuts", "time"): The company name created is "tonuts dime".
- ("donuts", "toffee"): The company name created is "tonuts doffee".
- ("time", "donuts"): The company name created is "dime tonuts".
- ("toffee", "donuts"): The company name created is "doffee tonuts".
Therefore, there are a total of 6 distinct company names.

The following are some examples of invalid selections:
- ("coffee", "time"): The name "toffee" formed after swapping already exists in the original array.
- ("time", "toffee"): Both names are still the same after swapping and exist in the original array.
- ("coffee", "toffee"): Both names formed after swapping already exist in the original array.

**Example 2:**

**Input:** ideas = ["lack","back"]
**Output:** 0
**Explanation:** There are no valid selections. Therefore, 0 is returned.

**Constraints:**

* `2 <= ideas.length <= 5 * 104`
* `1 <= ideas[i].length <= 10`
* `ideas[i]` consists of lowercase English letters.
* All the strings in `ideas` are **unique**.

# Approaches
## Brute-Force with Hash Set
This approach directly translates the problem statement into code. It iterates through every possible pair of distinct ideas `(ideaA, ideaB)`. For each pair, it simulates the swapping of the first letters and then checks if the two newly formed strings exist in the original set of ideas. To make the existence check efficient, the original `ideas` array is first converted into a `HashSet`.
**Time:** O(N^2 * L), where N is the number of ideas and L is their average length. The nested loops result in O(N^2) pairs, and for each pair, string operations and hash lookups take O(L) time. · **Space:** O(N * L), where N is the number of ideas and L is the average length of an idea. This space is used to store the `HashSet`.
**Pros:** Simple to understand and implement as it directly models the process described in the problem.
**Cons:** The time complexity is quadratic, O(N^2 * L), which is too slow for the given constraints (N up to 50,000) and will result in a 'Time Limit Exceeded' error.
### Explanation
The brute-force method systematically checks every combination of two distinct names from the input list. To begin, we put all the names into a `HashSet` to make searching for a name a very fast operation. Then, we use nested loops to select every unique pair of names, `ideaA` and `ideaB`. For each pair, we perform the described swap of their first letters to create `newA` and `newB`. The crucial step is then to check if both of these newly created names are absent from our initial `HashSet`. If neither `newA` nor `newB` exists in the original set of ideas, we've found a valid combination. Since the problem considers `(ideaA, ideaB)` and `(ideaB, ideaA)` as forming two distinct company names, we increment our total count by 2 for each such valid unordered pair found. This process is repeated until all pairs have been checked.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long namingCompany(String[] ideas) {
        Set<String> ideaSet = new HashSet<>();
        for (String idea : ideas) {
            ideaSet.add(idea);
        }

        long validNames = 0;
        for (int i = 0; i < ideas.length; i++) {
            for (int j = i + 1; j < ideas.length; j++) {
                String ideaA = ideas[i];
                String ideaB = ideas[j];

                char charA = ideaA.charAt(0);
                char charB = ideaB.charAt(0);

                if (charA == charB) {
                    continue;
                }

                String suffixA = ideaA.substring(1);
                String suffixB = ideaB.substring(1);

                String newA = charB + suffixA;
                String newB = charA + suffixB;

                if (!ideaSet.contains(newA) && !ideaSet.contains(newB)) {
                    // The pair (ideaA, ideaB) is valid.
                    // The pair (ideaB, ideaA) is also valid and forms a distinct name.
                    validNames += 2;
                }
            }
        }
        return validNames;
    }
}
```
### Algorithm
*   Create a `HashSet` from the input `ideas` array to allow for fast lookups (O(1) on average).
*   Initialize a `long` counter, `validNames`, to zero.
*   Iterate through all possible pairs of distinct ideas using two nested loops. Let the ideas be `ideaA` and `ideaB`.
*   For each pair, extract their first characters, `charA` and `charB`, and their suffixes, `suffixA` and `suffixB`.
*   Construct the two new potential names by swapping the first letters: `newA = charB + suffixA` and `newB = charA + suffixB`.
*   Check if both `newA` and `newB` are **not** present in the original `HashSet` of ideas.
*   If the condition holds, it means we have found a valid pair. Since the problem counts ordered pairs (`ideaA ideaB` is distinct from `ideaB ideaA`), and our loops `(i, j)` with `j > i` only consider each pair once, we add 2 to our `validNames` counter.
*   After checking all pairs, return the final `validNames` count.

## Grouping by Initial Letter
A more efficient approach involves grouping the ideas based on their first letter. The validity of a company name `ideaA ideaB` depends on whether swapping the initial characters creates new words that already exist. This check can be optimized by focusing on the suffixes. If `ideaA = charA + suffixA` and `ideaB = charB + suffixB`, the new words are `charB + suffixA` and `charA + suffixB`. These new words exist in the original set only if `suffixA` is a suffix for some word starting with `charB`, and `suffixB` is a suffix for some word starting with `charA`. By pre-grouping suffixes by their initial letter, we can use combinatorics to count valid pairs much faster.
**Time:** O(N * L). The initial grouping takes O(N * L). The second part involves a constant number of comparisons between character groups (26*25/2). The work for each comparison is proportional to the size of the suffix sets. The total work across all comparisons is bounded by O(N * L), making the overall complexity dominated by the initial grouping step. · **Space:** O(N * L), where N is the number of ideas and L is their average length. This space is required to store all the suffixes grouped by their initial character.
**Pros:** Significantly more efficient, with a time complexity that is effectively linear in the total number of characters.; Passes the time limits for the given constraints by avoiding the O(N^2) check of all pairs.
**Cons:** More complex to reason about and implement compared to the brute-force approach.; Requires more space to store the grouped suffixes.
### Explanation
This optimized approach avoids the O(N^2) complexity by changing the perspective. Instead of comparing every pair of words, we compare every pair of initial letters. 

First, we categorize all ideas by their starting letter. For each letter from 'a' to 'z', we create a set containing the suffixes of all words that start with that letter. For example, if `ideas` contains `"coffee"` and `"car"`, the set for 'c' would be `{"offee", "ar"}`.

Once we have these groups, we iterate through every possible pair of distinct starting letters, say `c1` and `c2`. Let the corresponding suffix sets be `S1` and `S2`. A valid company name can be formed by picking `ideaA = c1 + s1` and `ideaB = c2 + s2` only if the new names `c2 + s1` and `c1 + s2` are not in the original `ideas` list. This condition holds if and only if `s1` is not in `S2` and `s2` is not in `S1`.

So, for the pair of letters `(c1, c2)`, we need to count how many suffixes in `S1` are not in `S2` (let this be `unique1`), and how many suffixes in `S2` are not in `S1` (let this be `unique2`). The number of valid pairs of ideas between these two groups is `unique1 * unique2`. Since the order of ideas matters, we multiply this by 2. We sum this value over all pairs of initial letters to get the total count.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long namingCompany(String[] ideas) {
        // Group suffixes by their starting character
        Set<String>[] groups = new HashSet[26];
        for (int i = 0; i < 26; i++) {
            groups[i] = new HashSet<>();
        }
        for (String idea : ideas) {
            groups[idea.charAt(0) - 'a'].add(idea.substring(1));
        }

        long answer = 0;
        // Compare every pair of groups
        for (int i = 0; i < 25; i++) {
            for (int j = i + 1; j < 26; j++) {
                Set<String> set1 = groups[i];
                Set<String> set2 = groups[j];

                long commonSuffixes = 0;
                for (String suffix : set1) {
                    if (set2.contains(suffix)) {
                        commonSuffixes++;
                    }
                }
                
                long uniqueInSet1 = set1.size() - commonSuffixes;
                long uniqueInSet2 = set2.size() - commonSuffixes;

                answer += 2 * uniqueInSet1 * uniqueInSet2;
            }
        }

        return answer;
    }
}
```
### Algorithm
*   Create an array of 26 `HashSet<String>`s, let's call it `groups`. `groups[i]` will store the suffixes of all ideas starting with the character `'a' + i`.
*   Iterate through the input `ideas` array. For each `idea`, add its suffix (`idea.substring(1)`) to the corresponding set in the `groups` array based on its first character.
*   Initialize a `long` counter `ans` to 0.
*   Iterate through all pairs of distinct characters from 'a' to 'z'. A nested loop `for i from 0 to 25` and `for j from i + 1 to 25` is suitable.
*   For each pair of indices `(i, j)`, get the corresponding suffix sets, `set1 = groups[i]` and `set2 = groups[j]`.
*   Calculate `commonSuffixes`, the number of suffixes that exist in both `set1` and `set2`. This can be done efficiently by iterating through the smaller set and checking for element existence in the larger set.
*   Calculate the number of suffixes that are unique to each group with respect to the other:
    *   `uniqueInSet1 = set1.size() - commonSuffixes`
    *   `uniqueInSet2 = set2.size() - commonSuffixes`
*   Any idea from `group_i` with a unique suffix can be paired with any idea from `group_j` with a unique suffix. The number of valid ordered pairs between these two groups is `uniqueInSet1 * uniqueInSet2`. Since order matters, we multiply by 2.
*   Add `2L * uniqueInSet1 * uniqueInSet2` to the total `ans`.
*   Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  long distinctNames(String[] ideas) {
    Set<String> s = new HashSet<>();
    for (String v : ideas) {
      s.add(v);
    }
    int[][] f = new int[26][26];
    for (String v : ideas) {
      char[] t = v.toCharArray();
      int i = t[0] - 'a';
      for (int j = 0; j < 26; ++j) {
        t[0] = (char)(j + 'a');
        if (!s.contains(String.valueOf(t))) {
          ++f[i][j];
        }
      }
    }
    long ans = 0;
    for (String v : ideas) {
      char[] t = v.toCharArray();
      int i = t[0] - 'a';
      for (int j = 0; j < 26; ++j) {
        t[0] = (char)(j + 'a');
        if (!s.contains(String.valueOf(t))) {
          ans += f[j][i];
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long distinctNames(vector<string> &ideas) {
    unordered_set<string> s(ideas.begin(), ideas.end());
    int f[26][26]{};
    for (auto v : ideas) {
      int i = v[0] - 'a';
      for (int j = 0; j < 26; ++j) {
        v[0] = j + 'a';
        if (!s.count(v)) {
          ++f[i][j];
        }
      }
    }
    long long ans = 0;
    for (auto &v : ideas) {
      int i = v[0] - 'a';
      for (int j = 0; j < 26; ++j) {
        v[0] = j + 'a';
        if (!s.count(v)) {
          ans += f[j][i];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def distinctNames(self, ideas: List[str]) -> int: s = set(ideas) f = [[0] * 26 for _ in range(26)] for v in ideas: i = ord(v[0]) - ord('a') t = list(v) for j in range(26): t[0] = chr(ord('a') + j) if '' . join(t) not in s: f[i][j] += 1 ans = 0 for v in ideas: i = ord(v[0]) - ord('a') t = list(v) for j in range(26): t[0] = chr(ord('a') + j) if '' . join(t) not in s: ans += f[j][i] return ans

```