In this guide, you will get 2306. Naming a Company LeetCode Solution with the best time and space complexity. The solution to Naming a Company problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 them ideaA and ideaB.
Swap the first letters of ideaA and ideaB with each other.
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.
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.
Complexity Analysis
Time Complexity: O(n) + O(26^2)
Space Complexity: O(n)
2306. Naming a Company LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
2306. Naming a Company LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
2306. Naming a Company LeetCode Solution in Python
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 # code by PROGIEZ
