Naming a Company
HardPrompt
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 themideaAandideaB. - Swap the first letters of
ideaAandideaBwith each other. - If both of the new names are not found in the original
ideas, then the nameideaA ideaB(the concatenation ofideaAandideaB, 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 * 1041 <= ideas[i].length <= 10ideas[i]consists of lowercase English letters.- All the strings in
ideasare unique.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a
HashSetfrom the inputideasarray to allow for fast lookups (O(1) on average). - Initialize a
longcounter,validNames, to zero. - Iterate through all possible pairs of distinct ideas using two nested loops. Let the ideas be
ideaAandideaB. - For each pair, extract their first characters,
charAandcharB, and their suffixes,suffixAandsuffixB. - Construct the two new potential names by swapping the first letters:
newA = charB + suffixAandnewB = charA + suffixB. - Check if both
newAandnewBare not present in the originalHashSetof ideas. - If the condition holds, it means we have found a valid pair. Since the problem counts ordered pairs (
ideaA ideaBis distinct fromideaB ideaA), and our loops(i, j)withj > ionly consider each pair once, we add 2 to ourvalidNamescounter. - After checking all pairs, return the final
validNamescount.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
- Create an array of 26
HashSet<String>s, let's call itgroups.groups[i]will store the suffixes of all ideas starting with the character'a' + i. - Iterate through the input
ideasarray. For eachidea, add its suffix (idea.substring(1)) to the corresponding set in thegroupsarray based on its first character. - Initialize a
longcounteransto 0. - Iterate through all pairs of distinct characters from 'a' to 'z'. A nested loop
for i from 0 to 25andfor j from i + 1 to 25is suitable. - For each pair of indices
(i, j), get the corresponding suffix sets,set1 = groups[i]andset2 = groups[j]. - Calculate
commonSuffixes, the number of suffixes that exist in bothset1andset2. 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() - commonSuffixesuniqueInSet2 = set2.size() - commonSuffixes
- Any idea from
group_iwith a unique suffix can be paired with any idea fromgroup_jwith a unique suffix. The number of valid ordered pairs between these two groups isuniqueInSet1 * uniqueInSet2. Since order matters, we multiply by 2. - Add
2L * uniqueInSet1 * uniqueInSet2to the totalans. - Return
ans.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.