Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2306.html

2306. Naming a Company

  • Difficulty: Hard.
  • Related Topics: Array, Hash Table, String, Bit Manipulation, Enumeration.
  • Similar Questions: .

Problem

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.

Solution

  • class Solution {
    private long count(Map<Character, Set<String>> map, char a, char b) {
        if (!map.containsKey(a) || !map.containsKey(b)) {
            return 0;
        }
        long common = 0;
        Set<String> first = map.get(a);
        Set<String> second = map.get(b);
        for (String c : first) {
            if (second.contains(c)) {
                common++;
            }
        }
        long uniqueA = first.size() - common;
        long uniqueB = second.size() - common;
        return uniqueA * uniqueB * 2L;
    }

    public long distinctNames(String[] ideas) {
        long ans = 0;
        Map<Character, Set<String>> map = new HashMap<>();
        for (String idea : ideas) {
            char startChar = idea.charAt(0);
            Set<String> values = map.getOrDefault(startChar, new HashSet<>());
            values.add(idea.substring(1));
            map.put(startChar, values);
        }
        for (int i = 0; i <= 26; i++) {
            for (int j = i + 1; j <= 26; j++) {
                long unique = count(map, (char) (i + 'a'), (char) (j + 'a'));
                ans += unique;
            }
        }
        return ans;
    }
}

############

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());
        vector<vector<int>> f(26, vector<int>(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 ans

############

# 2306. Naming a Company
# https://leetcode.com/problems/naming-a-company/

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        n = len(ideas)
        counts = [[0] * 26 for _ in range(26)]
        seen = set(ideas)
        orda = ord("a")
        
        for idea in ideas:
            for c in range(26):
                if chr(orda + c) + idea[1:] not in seen:
                    counts[ord(idea[0]) - orda][c] += 1
        
        res = 0
        
        for idea in ideas:
            for c in range(26):
                if chr(orda + c) + idea[1:] not in seen:
                    res += counts[c][ord(idea[0]) - orda]
        
        return res
                
        


  • func distinctNames(ideas []string) int64 {
	s := map[string]bool{}
	for _, v := range ideas {
		s[v] = true
	}
	f := make([][]int, 26)
	for i := range f {
		f[i] = make([]int, 26)
	}
	for _, v := range ideas {
		i := int(v[0] - 'a')
		t := []byte(v)
		for j := 0; j < 26; j++ {
			t[0] = 'a' + byte(j)
			if !s[string(t)] {
				f[i][j]++
			}
		}
	}
	var ans int64
	for _, v := range ideas {
		i := int(v[0] - 'a')
		t := []byte(v)
		for j := 0; j < 26; j++ {
			t[0] = 'a' + byte(j)
			if !s[string(t)] {
				ans += int64(f[j][i])
			}
		}
	}
	return ans
}

  • function distinctNames(ideas: string[]): number {
    const s = new Set(ideas);
    const f: number[][] = Array(26)
        .fill(0)
        .map(() => Array(26).fill(0));
    for (const v of s) {
        const i = v.charCodeAt(0) - 'a'.charCodeAt(0);
        const t = [...v];
        for (let j = 0; j < 26; ++j) {
            t[0] = String.fromCharCode('a'.charCodeAt(0) + j);
            if (!s.has(t.join(''))) {
                f[i][j]++;
            }
        }
    }
    let ans = 0;
    for (const v of s) {
        const i = v.charCodeAt(0) - 'a'.charCodeAt(0);
        const t = [...v];
        for (let j = 0; j < 26; ++j) {
            t[0] = String.fromCharCode('a'.charCodeAt(0) + j);
            if (!s.has(t.join(''))) {
                ans += f[j][i];
            }
        }
    }
    return ans;
}

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions