[Solved] Naming a Company LeetCode Contest Problem

Naming a Company: 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.

Solution:

Explanation:

Group strings from ideas into different sets by their initials.
For example:

• set c = {“offee”, “hord”, “ome”, …}
• set b = {“offee”, “ee”, “uffalo”, …}

For two words A = a + suffix_a, B = b + suffix_b with different initials a, b, if the suffix of A (suffix_a) appears in both sets, but they can’t form a valid name. Thus we just need to find out the number of unique suffix from set A and set B .

• “offee” appears in both sets thus it can’t form a valid name.
• “hord”, “ome”, “ee” and “uffalo” are unique suffixes.

“”hord” with “ee” and vise versa, …, we can make a total of 2 * 2 * 2 valid names.

def distinctNames(self, ideas: List[str]) -> int:
        # Group strings by their initials
        A = [set() for _ in range(26)]
        for idea in ideas:
            A[ord(idea[0]) - ord('a')].add(idea[1:])
        
        ans = 0
        # Find name from every character pair.
        for i in range(25):
            for j in range(i + 1, 26):
                k = len(A[i] & A[j]) # Number of duplicated rest part
                ans += 2 * (len(A[i]) - k) * (len(A[j]) - k)
        return ans

Let’s create a 2D vector arr of size 26 x 26 in which every arr[i][j] stores whether the word starting with i-‘a’ can swap with the symbol j+’a’.
For eg. for ideas = [“coffee”,”donuts”,”time”,”toffee”]
the created array will have arr[2][3] = 1,arr[3][2] =1,arr[3][19]=1,arr[19][2] = 1,arr[19][3]=2 i.e.1+1(from time and toffee)

Space Complexity: O(n) (considering 26×26 array as constant space)

Time Complexity: O(n)

unordered_map<string,bool> hm;
        for(int i=0;i<ideas.size();i++){      
             hm[ideas[i]] = true;
        }
        
        vector<vector<long long >> dict(26,vector<long long >(26,0)); 
        
        for(int i =0;i<ideas.size();i++){
            
            string word = ideas[i].substr(1);
            
            int in = ideas[i][0]-'a';
            
              for(int j = 0;j<26;j++){
                  char y = ('a'+j);
                  string temp = y + word;
                  
                  if(hm.count(temp)==0){
                      dict[in][j] += 1;
                  }   
              }}
        
        long long count = 0;
        for(int i=0;i<26;i++){
            
              for(int j = 0;j<26;j++){
                  if(i==j)continue;
                  if(dict[i][j]>0){
                      count += (dict[j][i]*dict[i][j]);   
                  }
              }  
        }
        
        return count;

Algorithm:

1. Count how many valid transformations from a word start with letter i to the letter j, record them in the counter array,
2. then for each letters combo (i, j), the total valid combos of (all words start with i, all words start with j) are counter[i][j] * counter[j][i]

class Solution {
    public long distinctNames(String[] ideas) {
        Set<String> set = new HashSet<>();
        for (String s: ideas) {
            set.add(s);
        }
        //counter[i][j] means the number of valid transformation that from words start with i to words start with j
        long[][] counter = new long[26][26];
        
        for (int i=0; i<ideas.length; i++) {
            StringBuilder sb = new StringBuilder(ideas[i]);
            char old = sb.charAt(0);
            for (char c='a'; c<='z'; c++) {
                if (c != old) {
                    sb.setCharAt(0, c);
                    if (!set.contains(sb.toString())) {
                        //found a valid transformation from (old) to (c)
                        counter[old-'a'][c-'a']++;
                    }
                }
            }
        }
        long result = 0;
        for (int i=0; i<26; i++) {
            for (int j=0; j<26; j++) {
                // num of words start with i that can transform to j * num of words start with j that can transform to i
                result += counter[i][j] * counter[j][i];
            }
        }
        return result;
        
    }
}

Happy Learning – If you require any further information, feel free to contact me.