2306. Naming a Company

Description

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 idea_A and idea_B.
Swap the first letters of idea_A and idea_B with each other.
If both of the new names are not found in the original ideas, then the name idea_A idea_B (the concatenation of idea_A and idea_B, 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 * 10⁴
1 <= ideas[i].length <= 10
ideas[i] consists of lowercase English letters.
All the strings in ideas are unique.

Solutions

Solution 1: Enumeration and Counting

Thinking

A valid name swaps the first letters of two distinct ideas, and both results must be absent from the original set. Pairwise checks are \(O(n^2)\) and fail for \(n \le 5 \times 10^4\).

There are only \(26\) first letters; whether suffixes collide decides a swap. After storing ideas in a set, count \(f[i][j]\): strings starting with letter \(i\) whose first letter can become \(j\) without hitting the set. A second pass adds \(f[j][i]\) for each idea that may swap to \(j\), counting pairs in \(O(n|\Sigma|)\) time.

We define \(f[i][j]\) to represent the number of strings in \(\textit{ideas}\) that start with the \(i\)-th letter and, when replaced with the \(j\)-th letter, do not exist in \(\textit{ideas}\). Initially, \(f[i][j] = 0\). Additionally, we use a hash table \(s\) to record the strings in \(\textit{ideas}\), allowing us to quickly determine whether a string is in \(\textit{ideas}\).

Next, we traverse the strings in \(\textit{ideas}\). For the current string \(v\), we enumerate the first letter \(j\) after replacement. If the string obtained by replacing \(v\) is not in \(\textit{ideas}\), we update \(f[i][j] = f[i][j] + 1\).

Finally, we traverse the strings in \(\textit{ideas}\) again. For the current string \(v\), we enumerate the first letter \(j\) after replacement. If the string obtained by replacing \(v\) is not in \(\textit{ideas}\), we update the answer \(\textit{ans} = \textit{ans} + f[j][i]\).

The final answer is \(\textit{ans}\).

The time complexity is \(O(n \times m \times |\Sigma|)\), and the space complexity is \(O(|\Sigma|^2)\). Here, \(n\) and \(m\) are the number of strings in \(\textit{ideas}\) and the maximum length of the strings, respectively, and \(|\Sigma|\) is the character set of the strings, with \(|\Sigma| \leq 26\) in this problem.

Python3JavaC++Go

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

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());
        int f[26][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;
    }
};

func distinctNames(ideas []string) (ans int64) {
    s := map[string]bool{}
    for _, v := range ideas {
        s[v] = true
    }
    f := [26][26]int{}
    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]++
            }
        }
    }

    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
}

2306. Naming a Company

Description

Solutions

Solution 1: Enumeration and Counting

Comments