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 themideaA
andideaB
. -
Swap the first letters of
ideaA
andideaB
with each other. -
If both of the new names are not found in the original
ideas
, then the nameideaA ideaB
(the concatenation ofideaA
andideaB
, 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).