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.
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.
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.
Contents
- Solution 1 - Group by starting letter of idea word and store distinct ideas into HashSet
The main intution behind this solution is that, since we have to swap 1st character only and find if that resultant word exists in original input array of ideas,
let say if the words are "coffee" and "toffee", then swaping the first lettter 'c' with 't' or 't' with 'c',
is going to result as the other word, so can skip checking such idea words.
So, in this approach, we will group the words by their starting letter into a HashSet, this means we will end up with 26
entries with words grouped by key as their startig letter. In this solution, we will use a temporary array ideasSet with size 26, where the index will represent the
indexes from letters 'a' to 'z' and the value is a HashSet with all the words starts with partiular letter,
but we will only store the substring starts from index 1, since we already knew the starting letter.
Then, we will loop through each entry in ideasSet in a nested loop, for each combination of starting letters, check how many repeated words are found
in both sets. For example, lets take a look at below example:
| Starting letter |
Group by set |
| c
| offee |
| d
| onut |
| t
| ime |
| offee |
Say, we want to check distinct words set between words starts with 'c' and 't', for each word that starts with 'c'
we will check whether they exist in the words set that thats with 't', since the word "offee" exists in both,
number of words exists in both count is 1. So, in this case, the distinct words are, "coffee" and "time".
So the number unique combinations can be formed are words size starts with 'a' -
words exists in both sets * words size starts with 't' -
words exists in both sets. But, we can form a company names by reversing the same words, so we can multiply the result with 2.
import java.util.HashSet;
public class NamingACompany {
static long distinctNames(String[] ideas) {
HashSet<String>[] set = new HashSet[26];
for(String idea: ideas) {
int index = idea.charAt(0) - 'a';
if(set[index] == null) {
set[index] = new HashSet<>();
}
set[index].add(idea.substring(1));
}
long result = 0;
for(int i=0; i<set.length; i++) {
HashSet<String> ideasASet = set[i];
if(ideasASet == null) {
continue;
}
for(int j=i; j<set.length; j++) {
HashSet<String> ideasBSet = set[j];
if(ideasBSet == null) {
continue;
}
int existInBoth = 0; // suffix words that exits in both sets
for(String ideasB: ideasBSet) {
if(ideasASet.contains(ideasB)) {
existInBoth++;
}
}
result += (ideasBSet.size() - existInBoth) * (ideasASet.size() - existInBoth) * 2L;
}
}
return result;
}
public static void main(String[] args) {
System.out.println(distinctNames(new String[]{"coffee","donuts","time","toffee"}));
System.out.println(distinctNames(new String[]{"lack","back"}));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the length of ideas array.
The actual time complexity will be (O 262 * n), since we have a nested loop with array size 26, and in each loop we are checking all the words of size n.
Space complexity: O(n), since we are storing words into array of HashSets.
Above implementations source code can be found at
GitHub link for Java code