2306. Naming a Company - Solution

Q: Is Naming a Company easy or hard?

Naming a Company is classified as a Hard problem because the brute force idea is simple but inefficient. The challenge is recognizing that grouping by first letter and counting shared suffixes removes redundant comparisons and dramatically improves performance.

Q: Naming a Company Python/Java solution

In Python, the solution typically uses a list of 26 sets and string slicing (idea[1:]) to store suffixes. Java implementations commonly use HashSet arrays indexed by the first character. Both versions iterate through prefix pairs and compute valid combinations mathematically.

The 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 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.

Approach overview

Problem Overview: You receive a list of idea names. Pick two ideas, swap their first letters, and form two new names. A pair is valid only if both newly formed names do not already exist in the original list. The task is to count how many distinct valid company name pairs can be created.

Approach 1: Brute Force Pair Enumeration (O(n² * L) time, O(n) space)

Check every pair of ideas using two nested loops. For each pair, swap the first characters and build the two new candidate strings. Use a HashSet to quickly verify whether either generated name already exists. If both are new, the pair contributes two valid company names (since order matters). This approach directly simulates the operation and is useful for understanding the constraints, but the quadratic pair checks make it impractical for large inputs.

Approach 2: Optimized Using Prefix Sets (O(n + 26² * k) time, O(n) space)

Instead of comparing every pair of full strings, group ideas by their first character and store only the suffix (everything after the first letter) in a hash set. This creates up to 26 groups. When comparing two groups i and j, compute how many suffixes they share. Shared suffixes would produce existing names after swapping prefixes, so they must be excluded. If group sizes are a and b and they share common suffixes, the number of valid combinations is (a - common) * (b - common) * 2. This avoids constructing every possible pair and reduces the search space to prefix group comparisons.

The optimization relies heavily on fast lookups provided by a hash table and grouping strings by their first character. Handling suffix sets efficiently keeps comparisons small even when the input size grows. The logic mainly involves string slicing and enumerating the 26 prefix groups stored in an array or list.

Recommended for interviews: Interviewers expect the prefix-group optimization. The brute force approach demonstrates the core idea of swapping characters and validating with a set, but the optimized solution shows you can reduce redundant comparisons by grouping data and counting valid combinations mathematically.

Approach 1: Brute Force Approach

In this approach, we will iterate over all possible pairs of ideas and attempt to swap their first letters to form new names. We will then check if these new names are unique by not being present in the original list of ideas. This approach straightforwardly uses nested loops to examine each pair, which results in an O(n^2) time complexity for the pair-wise name generation.

Python

def count_valid_names(ideas):
    def is_valid_name(a, b, idea_set):
        swapped_a = b[0] + a[1:]
        swapped_b = a[0] + b[1:]
        return swapped_a not in idea_set and swapped_b not in idea_set

    idea_set = set(ideas)
    valid_names = 0
    
    for i in range(len(ideas)):
        for j in range(i + 1, len(ideas)):
            if is_valid_name(ideas[i], ideas[j], idea_set):
                valid_names += 1
    
    return valid_names * 2

ideas = ["coffee", "donuts", "time", "toffee"]
print(count_valid_names(ideas))

Java

import java.util.*;

public class NamingCompany {
  
    public static boolean isValidName(StringBuilder a, StringBuilder b, Set<String> ideaSet) {
        char temp = a.charAt(0);
        a.setCharAt(0, b.charAt(0));
        b.setCharAt(0, temp);

        boolean valid = !ideaSet.contains(a.toString()) && !ideaSet.contains(b.toString());

        // Swap back
        a.setCharAt(0, temp);
        b.setCharAt(0, a.charAt(0));
        
        return valid;
    }

    public static int countValidNames(String[] ideas) {
        int validNames = 0;
        Set<String> ideaSet = new HashSet<>(Arrays.asList(ideas));
        int ideasSize = ideas.length;

        for (int i = 0; i < ideasSize; i++) {
            for (int j = i + 1; j < ideasSize; j++) {
                if (isValidName(new StringBuilder(ideas[i]), new StringBuilder(ideas[j]), ideaSet)) {
                    validNames++;
                }
            }
        }

        return validNames * 2; // Counting both (a,b) and (b,a)
    }

    public static void main(String[] args) {
        String[] ideas = {"coffee", "donuts", "time", "toffee"};
        System.out.println(countValidNames(ideas));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

bool isValidName(std::string &a, std::string &b, std::unordered_set<std::string> &ideaSet) {
    char temp = a[0];
    a[0] = b[0];
    b[0] = temp;

    bool valid = ideaSet.find(a) == ideaSet.end() && ideaSet.find(b) == ideaSet.end();

    // Swap back the first letters
    a[0] = temp;
    b[0] = a[0];

    return valid;
}

int countValidNames(std::vector<std::string> &ideas) {
    int validNames = 0;
    std::unordered_set<std::string> ideaSet(ideas.begin(), ideas.end());
    int ideasSize = ideas.size();

    for (int i = 0; i < ideasSize; i++) {
        for (int j = i + 1; j < ideasSize; j++) {
            if (isValidName(ideas[i], ideas[j], ideaSet)) {
                validNames++;
            }
        }
    }

    return validNames * 2; // Since (a,b) and (b,a) both should be counted
}

int main() {
    std::vector<std::string> ideas = {"coffee", "donuts", "time", "toffee"};
    std::cout << countValidNames(ideas) << std::endl;
    return 0;
}

JavaScript

function countValidNames(ideas) {
    const ideaSet = new Set(ideas);
    let validNames = 0;

    for (let i = 0; i < ideas.length; i++) {
        for (let j = i + 1; j < ideas.length; j++) {
            const a = ideas[i];
            const b = ideas[j];

            const swappedA = b[0] + a.substring(1);
            const swappedB = a[0] + b.substring(1);

            if (!ideaSet.has(swappedA) && !ideaSet.has(swappedB)) {
                validNames++;
            }
        }
    }

    return validNames * 2; // Counting both (a,b) and (b,a)
}

const ideas = ["coffee", "donuts", "time", "toffee"];
console.log(countValidNames(ideas));

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int isValidName(char *a, char *b, char **ideas, int ideasCount) {
    char temp;
    temp = a[0];
    a[0] = b[0];
    b[0] = temp;

    for (int i = 0; i < ideasCount; i++) {
        if (strcmp(a, ideas[i]) == 0 || strcmp(b, ideas[i]) == 0) {
            // Swap back and return false as they exist
            temp = a[0];
            a[0] = b[0];
            b[0] = temp;
            return 0;
        }
    }

    // Swap back the first letter after checking
    temp = a[0];
    a[0] = b[0];
    b[0] = temp;

    return 1;
}

int countValidNames(char **ideas, int ideasSize) {
    int validNames = 0;

    for (int i = 0; i < ideasSize; i++) {
        for (int j = i + 1; j < ideasSize; j++) {
            if (isValidName(ideas[i], ideas[j], ideas, ideasSize)) {
                validNames++;
            }
        }
    }

    return validNames * 2; // Since (a,b) and (b,a) both should be counted
}

int main() {
    char *ideas[] = {"coffee", "donuts", "time", "toffee"};
    int ideasSize = sizeof(ideas) / sizeof(ideas[0]);
    printf("%d\n", countValidNames(ideas, ideasSize));
    return 0;
}

using System;
using System.Collections.Generic;

public class NamingCompany {
    public static bool IsValidName(string a, string b, HashSet<string> ideaSet) {
        string swappedA = b[0] + a.Substring(1);
        string swappedB = a[0] + b.Substring(1);

        return !ideaSet.Contains(swappedA) && !ideaSet.Contains(swappedB);
    }

    public static int CountValidNames(string[] ideas) {
        int validNames = 0;
        HashSet<string> ideaSet = new HashSet<string>(ideas);
        int ideasSize = ideas.Length;

        for (int i = 0; i < ideasSize; i++) {
            for (int j = i + 1; j < ideasSize; j++) {
                if (IsValidName(ideas[i], ideas[j], ideaSet)) {
                    validNames++;
                }
            }
        }

        return validNames * 2; // Consider both (a,b) and (b,a)
    }

    public static void Main(string[] args) {
        string[] ideas = { "coffee", "donuts", "time", "toffee" };
        Console.WriteLine(CountValidNames(ideas));
    }
}

This Python code uses set operations for fast membership checking. It swaps the initial characters of the names in a pair, checks for uniqueness, and increments the valid name count if both swapped names are not in the original list.

Complexity

Time Complexity: O(n^2 * m), where n is the number of ideas and m is the average length of the names.
Space Complexity: O(n) for storing ideas in a set for rapid access.

Try this approach in the editor

Approach 2: Optimized Approach Using Prefix Sets

This improved approach seeks to avoid redundant swaps by organizing names into groups based on their prefix letters. If two sets have no overlap with original names when swapping the first characters of the names from those sets, we count the combinations. By limiting unnecessary swaps, this method reduces repetitive calculations.

Python

def count_valid_names_optimized(ideas):
    from collections import defaultdict
    prefix_dict = defaultdict(set)

    for idea in ideas:
        prefix_dict[idea[0]].add(idea)

    valid_names = 0
    prefixes = list(prefix_dict.keys())

    for i in range(len(prefixes)):
        for j in range(i + 1, len(prefixes)):
            for a in prefix_dict[prefixes[i]]:
                for b in prefix_dict[prefixes[j]]:
                    if (b[0] + a[1:] not in prefix_dict[prefixes[i]]) and (a[0] + b[1:] not in prefix_dict[prefixes[j]]):
                        valid_names += 1

    return valid_names * 2

ideas = ["coffee", "donuts", "time", "toffee"]
print(count_valid_names_optimized(ideas))

Java

import java.util.*;

public class NamingCompanyOptimized {
    public static int countValidNamesOptimized(String[] ideas) {
        List<Set<String>> prefixSets = new ArrayList<>(Collections.nCopies(26, new HashSet<>()));
        int validNames = 0;

        // Group ideas by their first character in prefixSets
        for (String idea : ideas) {
            char firstChar = idea.charAt(0);
            prefixSets.get(firstChar - 'a').add(idea);
        }

        // Compare each set of prefixed names
        for (int i = 0; i < 26; i++) {
            for (int j = i + 1; j < 26; j++) {
                for (String a : prefixSets.get(i)) {
                    for (String b : prefixSets.get(j)) {
                        String swappedA = a.replace(a.charAt(0), b.charAt(0));
                        String swappedB = b.replace(b.charAt(0), a.charAt(0));

                        if (!prefixSets.get(i).contains(swappedB) && !prefixSets.get(j).contains(swappedA)) {
                            validNames++;
                        }
                    }
                }
            }
        }

        return validNames * 2; // Count both (a,b) and (b,a)
    }

    public static void main(String[] args) {
        String[] ideas = { "coffee", "donuts", "time", "toffee" };
        System.out.println(countValidNamesOptimized(ideas));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

int countValidNamesOptimized(const std::vector<std::string> &ideas) {
    std::vector<std::unordered_set<std::string>> prefixSets(26);
    int validNames = 0;

    // Group ideas by their first character in prefixSets
    for (const std::string &idea : ideas) {
        char firstChar = idea[0];
        prefixSets[firstChar - 'a'].insert(idea);
    }

    // Compare each set of prefixed names
    for (int i = 0; i < 26; i++) {
        for (int j = i + 1; j < 26; j++) {
            for (const std::string &a : prefixSets[i]) {
                for (const std::string &b : prefixSets[j]) {
                    std::string swappedA = b;
                    std::string swappedB = a;
                    swappedA[0] = a[0];
                    swappedB[0] = b[0];

                    if (prefixSets[i].find(swappedA) == prefixSets[i].end() && prefixSets[j].find(swappedB) == prefixSets[j].end()) {
                        validNames++;
                    }
                }
            }
        }
    }

    return validNames * 2; // Count both (a,b) and (b,a)
}

int main() {
    std::vector<std::string> ideas = {"coffee", "donuts", "time", "toffee"};
    std::cout << countValidNamesOptimized(ideas) << std::endl;
    return 0;
}

JavaScript

function countValidNamesOptimized(ideas) {
    const prefixMap = new Map();

    // Create a map of sets based on first character of each idea
    ideas.forEach(idea => {
        const firstChar = idea[0];
        if (!prefixMap.has(firstChar)) {
            prefixMap.set(firstChar, new Set());
        }
        prefixMap.get(firstChar).add(idea);
    });

    let validNames = 0;
    const keys = Array.from(prefixMap.keys());

    for (let i = 0; i < keys.length; i++) {
        for (let j = i + 1; j < keys.length; j++) {
            const setA = prefixMap.get(keys[i]);
            const setB = prefixMap.get(keys[j]);
            for (const ideaA of setA) {
                for (const ideaB of setB) {
                    const swappedA = ideaB[0] + ideaA.slice(1);
                    const swappedB = ideaA[0] + ideaB.slice(1);
                    if (!setA.has(swappedB) && !setB.has(swappedA)) {
                        validNames++;
                    }
                }
            }
        }
    }

    return validNames * 2; // Count (a, b) and (b, a)
}

const ideas = ["coffee", "donuts", "time", "toffee"];
console.log(countValidNamesOptimized(ideas));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool checkInSet(char *str, char **set, int size) {
    for (int i = 0; i < size; i++) {
        if (strcmp(str, set[i]) == 0) {
            return true;
        }
    }
    return false;
}

int countValidNamesOptimized(char **ideas, int ideasSize) {
    char *prefixSet[26][ideasSize];
    int prefixCount[26] = {0};
    int validNames = 0;

    // Group ideas by their first character into prefixSet
    for (int i = 0; i < ideasSize; i++) {
        char firstChar = ideas[i][0];
        prefixSet[firstChar - 'a'][prefixCount[firstChar - 'a']++] = ideas[i];
    }

    // Compare each set of prefixed names
    for (int i = 0; i < 26; i++) {
        for (int j = i + 1; j < 26; j++) {
            if (prefixCount[i] == 0 || prefixCount[j] == 0) continue;
            for (int m = 0; m < prefixCount[i]; m++) {
                for (int n = 0; n < prefixCount[j]; n++) {
                    char swappedA[11], swappedB[11];
                    strcpy(swappedA, prefixSet[j][n]);
                    swappedA[0] = prefixSet[i][m][0];

                    strcpy(swappedB, prefixSet[i][m]);
                    swappedB[0] = prefixSet[j][n][0];

                    if (!checkInSet(swappedA, ideas, ideasSize) && !checkInSet(swappedB, ideas, ideasSize)) {
                        validNames++;
                    }
                }
            }
        }
    }

    return validNames * 2; // Since (a,b) and (b,a) both should be counted
}

int main() {
    char *ideas[] = {"coffee", "donuts", "time", "toffee"};
    int ideasSize = sizeof(ideas) / sizeof(ideas[0]);
    printf("%d\n", countValidNamesOptimized(ideas, ideasSize));
    return 0;
}

using System;
using System.Collections.Generic;

public class NamingCompanyOptimized {
    public static int CountValidNamesOptimized(string[] ideas) {
        Dictionary<char, HashSet<string>> prefixDict = new Dictionary<char, HashSet<string>>();

        foreach (string idea in ideas) {
            char prefix = idea[0];
            if (!prefixDict.ContainsKey(prefix))
                prefixDict[prefix] = new HashSet<string>();
            prefixDict[prefix].Add(idea);
        }

        int validNames = 0;
        var prefixes = new List<char>(prefixDict.Keys);

        for (int i = 0; i < prefixes.Count; i++) {
            for (int j = i + 1; j < prefixes.Count; j++) {
                foreach (var a in prefixDict[prefixes[i]]) {
                    foreach (var b in prefixDict[prefixes[j]]) {
                        string swappedA = b[0] + a.Substring(1);
                        string swappedB = a[0] + b.Substring(1);
                        if (!prefixDict[prefixes[i]].Contains(swappedB) && !prefixDict[prefixes[j]].Contains(swappedA)) {
                            validNames++;
                        }
                    }
                }
            }
        }

        return validNames * 2;
    }

    public static void Main(string[] args) {
        string[] ideas = { "coffee", "donuts", "time", "toffee" };
        Console.WriteLine(CountValidNamesOptimized(ideas));
    }
}

Optimized Python solution utilizes prefix-based dictionaries for swift group setup, permitting fewer pairing and swap checks. This greatly minimizes overlap and test redundancy, leading to higher execution efficiency.

Complexity

Time Complexity: O(n^2) considering diminished overlap within certain prefix sets.
Space Complexity: O(n) to accommodate set-based classification of ideas by prefixes.

Try this approach in the editor

Approach 3: Enumeration and Counting

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

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

Finally, we traverse the strings in 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 ideas, we update the answer ans = ans + f[j][i].

The final answer is 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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n^2 * m), where n is the number of ideas and m is the average length of the names. Space Complexity: O(n) for storing ideas in a set for rapid access.
Optimized Approach Using Prefix Sets	Time Complexity: O(n^2) considering diminished overlap within certain prefix sets. Space Complexity: O(n) to accommodate set-based classification of ideas by prefixes.
Enumeration and Counting	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Pair Enumeration	O(n² * L)	O(n)	Useful for understanding the swapping logic or when the number of ideas is very small.
Prefix Grouping with Suffix Hash Sets	O(n + 26² * k)	O(n)	Best general solution. Efficient for large inputs by avoiding pairwise string comparisons.

Frequently asked questions

Is Naming a Company easy or hard?

Naming a Company is classified as a Hard problem because the brute force idea is simple but inefficient. The challenge is recognizing that grouping by first letter and counting shared suffixes removes redundant comparisons and dramatically improves performance.

Naming a Company Python/Java solution

In Python, the solution typically uses a list of 26 sets and string slicing (idea[1:]) to store suffixes. Java implementations commonly use HashSet<String> arrays indexed by the first character. Both versions iterate through prefix pairs and compute valid combinations mathematically.

How to solve Naming a Company in O(n)?

Pure O(n) is difficult because groups must still be compared, but the optimized solution is close. First group ideas by their starting letter and store suffixes in hash sets. For every pair of letters, count common suffixes and compute valid combinations using (sizeA - common) * (sizeB - common) * 2. Since there are only 26 possible prefixes, the comparison cost remains small.

What is the best approach for Naming a Company?

The most efficient solution groups ideas by their first letter and stores their suffixes in hash sets. For each pair of starting letters, count overlapping suffixes and subtract them from both groups to compute valid swaps. This reduces the work to comparing at most 26 prefix groups instead of all string pairs. The approach runs in roughly O(n + 26² * k) time with O(n) space.

Is Naming a Company asked at Google/Amazon/Meta?

Problems involving string grouping, hashing, and combinatorial counting are common in interviews at companies like Google, Amazon, and Meta. Naming a Company tests your ability to avoid brute force comparisons and instead aggregate data using hash sets and prefix grouping.

What data structure is used in Naming a Company?

The optimized solution relies mainly on hash sets (or hash tables) to store suffixes for each starting letter. An array or list of 26 sets is typically used to represent groups for each alphabet letter, enabling fast membership checks and efficient intersection counting.

What is the time complexity of Naming a Company?

The brute force approach checks every pair of ideas and takes O(n² * L) time where L is the average string length. The optimized prefix-group solution runs in O(n + 26² * k) time, where k is the average number of suffixes per group. Space complexity for the optimized method is O(n) due to storing suffix sets.

Naming a Company solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Approach Using Prefix Sets

Approach 3: Enumeration and Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Naming a Company solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Approach Using Prefix Sets

Approach 3: Enumeration and Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems