2306. Naming a Company
Description
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:
- Choose 2 distinct names from
ideas
, call themideaA
andideaB
. - Swap the first letters of
ideaA
andideaB
with each other. - If both of the new names are not found in the original
ideas
, then the nameideaA ideaB
(the concatenation ofideaA
andideaB
, separated by a space) is a valid company name. - 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.
Solutions
Solution 1: Enumeration and Counting
We define $f[i][j]$ to represent the number of strings in $\textit{ideas}$ that start with the $i$-th letter and, when replaced with the $j$-th letter, do not exist in $\textit{ideas}$. Initially, $f[i][j] = 0$. Additionally, we use a hash table $s$ to record the strings in $\textit{ideas}$, allowing us to quickly determine whether a string is in $\textit{ideas}$.
Next, we traverse the strings in $\textit{ideas}$. For the current string $v$, we enumerate the first letter $j$ after replacement. If the string obtained by replacing $v$ is not in $\textit{ideas}$, we update $f[i][j] = f[i][j] + 1$.
Finally, we traverse the strings in $\textit{ideas}$ again. For the current string $v$, we enumerate the first letter $j$ after replacement. If the string obtained by replacing $v$ is not in $\textit{ideas}$, we update the answer $\textit{ans} = \textit{ans} + f[j][i]$.
The final answer is $\textit{ans}$.
The time complexity is $O(n \times m \times |\Sigma|)$, and the space complexity is $O(|\Sigma|^2)$. Here, $n$ and $m$ are the number of strings in $\textit{ideas}$ and the maximum length of the strings, respectively, and $|\Sigma|$ is the character set of the strings, with $|\Sigma| \leq 26$ in this problem.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
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 26 27 28 29 30 31 |
|
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 26 27 |
|
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 26 27 28 29 |
|