We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Naming a Company

Number: 2390

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a list of unique strings (ideas), determine how many valid company names can be formed by choosing two distinct ideas, swapping their first letters, and ensuring that both newly formed names are not already present in the original list.

Key Insights

  • The critical observation is that only the first character changes while the suffix (the remaining part of the string) stays the same.
  • For every idea, separate the first letter from the suffix.
  • Group ideas by their starting letter to quickly check what suffixes each letter group has.
  • When considering two distinct first letters, the number of valid swaps depends on the number of suffixes that are unique to each group (i.e., suffixes that do not appear in the other group).
  • For each pair of letters (i, j), if there are common suffixes, they cannot be used because swapping would produce an existing name.
  • Count valid combinations as 2 * (|group[i]| - common) * (|group[j]| - common) to cover both swapping orders.

Space and Time Complexity

Time Complexity: O(26^2 * L) where L is the average length of an idea. In practice the constants are small due to only 26 possible starting letters. Space Complexity: O(n) to store the groups of suffixes for all the ideas.

Solution

The solution involves:

  1. Iterating over the ideas and splitting each idea into its first letter and its suffix.
  2. Using a dictionary (or similar data structure) where the key is the starting letter and the value is a set of suffixes for that letter.
  3. Checking every pair of distinct starting letters. For each pair:
    • Determine the number of common suffixes between the two sets.
    • Count the valid combinations using the difference in the size of each set and the common count.
  4. Multiply by 2 because each valid pair can generate two distinct valid names (swapping orders).
  5. Sum over all valid pairs and return the result.

Code Solutions

# Python solution with detailed comments
class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        # Create a dictionary to map first letter to a set of suffixes
        groups = {}
        for idea in ideas:
            first, suffix = idea[0], idea[1:]
            if first not in groups:
                groups[first] = set()
            groups[first].add(suffix)
        
        result = 0
        # Compare each pair of distinct first letters
        letters = list(groups.keys())
        for i in range(len(letters)):
            for j in range(i + 1, len(letters)):
                letter1 = letters[i]
                letter2 = letters[j]
                # Count the number of common suffixes between the two sets
                common = 0
                for suffix in groups[letter1]:
                    if suffix in groups[letter2]:
                        common += 1
                # Calculate valid combinations for this pair of letters
                count1 = len(groups[letter1]) - common
                count2 = len(groups[letter2]) - common
                result += 2 * count1 * count2  # multiply by 2 for both orders
        return result
← Back to All Questions