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:

  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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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:

1
2
3

Input: ideas = ["lack","back"]
Output: 0
Explanation: There are no valid selections. Therefore, 0 is returned.

Solution

Method 1 - Using Set

Here is the approach:

  1. Convert to Set: For fast look-up, we convert the list of ideas into a set.
  2. Nested Loops: We use nested loops to check each pair of ideas.
  3. Swapping First Letters: For each pair, we swap the first letters to create two new potential names.
  4. Validation: We check if both new names are not in the set of original ideas.
  5. Count Valid Names: If both new names are not found in the set, we count it as a valid company name.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int distinctNames(String[] ideas) {
        // Convert the ideas array into a set for fast look-up
        Set<String> set = new HashSet<>();
        for (String idea : ideas) {
            set.add(idea);
        }
        
        int ans = 0;
        // Use nested loops to compare each pair of ideas
        for (int i = 0; i < ideas.length; i++) {
            for (int j = i + 1; j < ideas.length; j++) {
                String ideaA = ideas[i];
                String ideaB = ideas[j];
                
                String swappedA = ideaB.charAt(0) + ideaA.substring(1);
                String swappedB = ideaA.charAt(0) + ideaB.substring(1);
                
                if (!set.contains(swappedA) && !set.contains(swappedB)) {
                    ans++;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        # Convert the ideas list into a set for fast look-up
        s: Set[str] = set(ideas)
        
        ans: int = 0
        # Use nested loops to compare each pair of ideas
        for i in range(len(ideas)):
            for j in range(i + 1, len(ideas)):
                idea_a = ideas[i]
                idea_b = ideas[j]
                
                swapped_a = idea_b[0] + idea_a[1:]
                swapped_b = idea_a[0] + idea_b[1:]
                
                if swapped_a not in s and swapped_b not in s:
                    ans += 1
        return ans

Complexity

  • ⏰ Time complexity: O(n^2 * m) where n is the number of ideas and m is the average length of an idea. The nested loops run in O(n^2), and the substring operations run in O(m).
  • 🧺 Space complexity: O(n). This is due to the set storing the original ideas.