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.

&nbsp;
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.


&nbsp;
Constraints:


	2 &lt;= ideas.length &lt;= 5 * 104
	1 &lt;= ideas[i].length &lt;= 10
	ideas[i] consists of lowercase English letters.
	All the strings in ideas are unique.


class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        
        names=defaultdict(set)
        res=0  
        
        #to store first letter as key and followed suffix as val
        for i in ideas:
            names[i[0]].add(i[1:])
            
        #list of distinct first-letters available in ideas (may or may not contain all alphabets,depends upon elements in ideas)
        arr=list(names.keys())
        ans,n=0,len(arr)
        
        for i in range(n):
            for j in range(i+1,n):
                #a,b => 2 distinct first letters
                a,b=arr[i],arr[j]
                # adding the number of distinct posssible suffixes and multiplying by 2 as the new word formed might be "newword1 newword2" or "newword2 newword1"
                res+=len(names[a]-names[b])*len(names[b]-names[a])*2
                
        return res
	
class Solution {
    public long distinctNames(String[] ideas) {
        // HashSet + String Manipulation; TC: O(26*26*n); SC: O(26*n)
        HashSet<String> [] arr = new HashSet[26];
        for(int i=0; i<26; i++) {
            arr[i] = new HashSet<>();
        }
        for(String s: ideas) {
            arr[s.charAt(0)-'a'].add(s.substring(1));
        }
        long ans=0, cnt;
        for(int i=0; i<26; i++) {
            for(int j=i+1; j<26; j++) {
                cnt=0;
                for(String str: arr[j]) {
                    if(arr[i].contains(str)) cnt++;
                }
                ans+=2*(arr[i].size()-cnt)*(arr[j].size()-cnt);
            }
        }
        return ans;
    }
}
class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_map <char,unordered_set<string>> mp;
        for(auto u : ideas) mp[u[0]].insert(u.substr(1,u.size()-1));
        
        long long ans = 0;
        
        for(int i = 0; i<26; i++){
            for(int j = i+1; j<26; j++){
                unordered_set <string> s1 = mp[i+'a'], s2 = mp[j+'a'];
                
                int comm = 0;
                for(auto u : s1)
                    if(s2.find(u)!=s2.end()) comm++;
                
                ans += (long long)(s1.size()-comm)*(long long)(s2.size()-comm)*2;
            }
        }
        return ans;
    }
};
/**
 * @param {string[]} ideas
 * @return {number}
 */
var distinctNames = function(ideas) {
    let res = 0;
    let lMap = new Map();

    for(let i=0; i<ideas.length; i++){
        let idea = ideas[i];
        // extract first letter
        let l = idea[0].charCodeAt() - 97;
        // extract substring
        let s = idea.substr(1);
        // group substring by first letter
        if(lMap.has(l)){
		    // must use map not array
            let m = lMap.get(l);
            m.set(s, 1);
            lMap.set(l, m);
        }else{
            let m = new Map();
            m.set(s, 1);
            lMap.set(l, m);
        }
    }

    for(let i=1; i<26; i++){
        for(let j=0; j<i; j++){
            // count substring with different first letter
            let m = 0;
            let m1 = lMap.has(i) ? lMap.get(i) : new Map();
            let m2 = lMap.has(j) ? lMap.get(j) : new Map();
			// both map must exist
            if(m1.size > 0 && m2.size > 0){
                let k1 = Array.from(m1.keys());
                for(let k=0; k<k1.length; k++){
                    if(m2.has(k1[k])){
                        m ++;
                    }
                }
                // the rest substring satisfy condition
                res += (m1.size - m) * (m2.size-m);
            }
        }
    }
    // double for count A + B and B + A
    res = res * 2;
    return res;    
};
Naming a Company