LeetCode 2306 - Naming a Company

Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, Bit Manipulation, Enumeration

Solution

Problem Understanding

The problem gives us a list of unique strings called ideas. We must repeatedly choose two different strings, swap their first characters, and determine whether the newly formed strings are both absent from the original list.

If both newly generated names do not already exist in ideas, then the ordered pair (ideaA, ideaB) forms a valid company name. The result we return is the total number of distinct valid ordered pairs.

The important detail is that order matters. If (coffee, donuts) is valid, then (donuts, coffee) is counted separately.

For example:

"coffee" and "donuts"
Swap first letters:
"coffee" becomes "doffee"
"donuts" becomes "conuts"
If neither "doffee" nor "conuts" exists in the original list, the pair is valid.

The constraints are large:

Up to 5 * 10^4 strings
Each string length up to 10

A naive comparison of every pair and every generated string would become too slow because there can be about 1.25 * 10^9 pairs in the worst case.

The problem guarantees that all original strings are unique, which simplifies membership checks because we can safely store everything in a hash set.

Several edge cases are important:

Two strings may already become existing words after swapping.
Different strings can share the same suffix.
Swapping may generate the exact same original strings.
Some starting letters may have no compatible swaps at all.
The answer can become large, so in Go we must use int64.

Approaches

Brute Force Approach

The most direct solution is to try every ordered pair of distinct ideas.

For each pair:

Swap the first characters.
Construct the two new strings.
Check whether either new string exists in the original set.
If both are absent, increment the answer.

This works because it explicitly simulates the operation described in the problem.

However, the complexity is too high.

If there are n strings, there are O(n^2) pairs. Each pair also requires string construction and hash lookups. With n = 5 * 10^4, this becomes infeasible.

Key Insight

The first character is the only part being swapped.

Suppose we split each word into:

first letter
suffix, meaning everything after the first character

Example:

Word	First Letter	Suffix
coffee	c	offee
donuts	d	onuts
time	t	ime

Now consider what makes a swap invalid.

If we swap first letters between two words:

c + onuts
d + offee

The swap fails if either generated word already exists.

Notice that existence depends entirely on whether a suffix already appears under another starting letter.

This suggests grouping words by first character.

For every starting letter:

store all suffixes associated with that letter

Then for two groups i and j:

find how many suffixes are shared
shared suffixes cannot participate in valid swaps
unique suffixes can pair freely

If:

unique_i = suffixes only in group i
unique_j = suffixes only in group j

Then the number of valid ordered pairs contributed by these groups is:

unique_i * unique_j * 2

The multiplication by 2 accounts for ordering.

Since there are only 26 lowercase letters, we only compare 26 groups, making the solution efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² * L)	O(n)	Explicitly tests every pair
Optimal	O(n + 26² * S)	O(n)	Groups suffixes by first character

Here:

n = number of ideas
L = average string length
S = average suffix set comparison cost

Because there are only 26 letters, the optimal solution is effectively linear in practice.

Algorithm Walkthrough

Step 1: Group suffixes by starting letter

Create 26 sets.

Each set stores the suffixes belonging to words that start with a particular character.

Example:

coffee -> c : offee
donuts -> d : onuts
time -> t : ime
toffee -> t : offee

Result:

c -> {offee}
d -> {onuts}
t -> {ime, offee}

We use sets because:

membership checks are O(1)
intersection operations become easy
duplicates are automatically avoided

Step 2: Compare every pair of starting letters

There are only 26 lowercase English letters.

For every pair (i, j) where i < j:

Compute the number of shared suffixes.
Shared suffixes cannot be swapped safely.

Suppose:

Group i size = A
Group j size = B
Shared suffixes = C

Then:

Unique to i = A - C
Unique to j = B - C

Every unique suffix from group i can pair with every unique suffix from group j.

That gives:

(A - C) * (B - C)

unordered pairs.

Since the problem counts ordered pairs:

2 * (A - C) * (B - C)

Add this to the answer.

Step 3: Return the final answer

After processing all 26 letter pairs, return the accumulated total.

Why it works

A swap is valid exactly when neither generated name already exists.

A generated name exists if its suffix already belongs to the target starting-letter group.

Therefore:

shared suffixes always produce invalid swaps
non-shared suffixes always produce valid swaps

By counting only suffixes unique to each group, we count exactly the valid combinations and avoid double counting.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        groups = [set() for _ in range(26)]

        for idea in ideas:
            first_index = ord(idea[0]) - ord('a')
            suffix = idea[1:]
            groups[first_index].add(suffix)

        answer = 0

        for i in range(26):
            for j in range(i + 1, 26):
                common_suffixes = len(groups[i] & groups[j])

                unique_i = len(groups[i]) - common_suffixes
                unique_j = len(groups[j]) - common_suffixes

                answer += 2 * unique_i * unique_j

        return answer

The implementation begins by creating 26 sets, one for each lowercase letter. Each word contributes its suffix into the set corresponding to its starting character.

The nested loop iterates through every pair of starting-letter groups. Since there are only 26 letters, this loop is very small and efficient.

The intersection operation:

groups[i] & groups[j]

finds suffixes shared by both groups. Those shared suffixes would recreate existing words after swapping, so they cannot contribute to valid names.

After subtracting the shared suffix count from each group size, we obtain the number of suffixes unique to each group. Multiplying these counts gives the number of valid unordered pairs, and multiplying by 2 converts them into ordered pairs.

Finally, the accumulated answer is returned.

Go Solution

func distinctNames(ideas []string) int64 {
	groups := make([]map[string]bool, 26)

	for i := 0; i < 26; i++ {
		groups[i] = make(map[string]bool)
	}

	for _, idea := range ideas {
		first := int(idea[0] - 'a')
		suffix := idea[1:]
		groups[first][suffix] = true
	}

	var answer int64 = 0

	for i := 0; i < 26; i++ {
		for j := i + 1; j < 26; j++ {
			common := 0

			for suffix := range groups[i] {
				if groups[j][suffix] {
					common++
				}
			}

			uniqueI := len(groups[i]) - common
			uniqueJ := len(groups[j]) - common

			answer += int64(2 * uniqueI * uniqueJ)
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version, but uses map[string]bool to simulate sets.

The answer uses int64 because the number of valid ordered pairs can exceed the range of a standard 32-bit integer.

Unlike Python, Go does not provide built-in set intersection operations, so we manually count shared suffixes by iterating through one map and checking membership in the other.

Worked Examples

Example 1

ideas = ["coffee","donuts","time","toffee"]

Step 1: Build groups

Word	Group	Suffix
coffee	c	offee
donuts	d	onuts
time	t	ime
toffee	t	offee

Result:

Letter	Suffix Set
c	{offee}
d	{onuts}
t	{ime, offee}

Step 2: Compare groups

Pair (c, d)

Value	Result
Common suffixes	0
Unique in c	1
Unique in d	1
Contribution	2 × 1 × 1 = 2

Valid ordered pairs:

(coffee, donuts)
(donuts, coffee)

Pair (c, t)

Shared suffix:

offee

Value	Result
Common suffixes	1
Unique in c	0
Unique in t	1
Contribution	0

No valid swaps.

Pair (d, t)

Value	Result
Common suffixes	0
Unique in d	1
Unique in t	2
Contribution	2 × 1 × 2 = 4

Valid ordered pairs:

(donuts, time)
(time, donuts)
(donuts, toffee)
(toffee, donuts)

Final Answer

2 + 0 + 4 = 6

Example 2

ideas = ["lack","back"]

Groups:

Letter	Suffix Set
l	{ack}
b	{ack}

Shared suffix count:

Thus:

unique_l = 0
unique_b = 0

Contribution:

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + 26² * S)	Building groups is linear, group comparisons are bounded by alphabet size
Space	O(n)	Stores all suffixes in sets

The dominant cost is storing suffixes and comparing set intersections. Since the alphabet size is fixed at 26, the pairwise comparison cost is effectively constant relative to n.

In practice, the algorithm performs close to linear time.

Test Cases

sol = Solution()

assert sol.distinctNames(
    ["coffee", "donuts", "time", "toffee"]
) == 6  # provided example

assert sol.distinctNames(
    ["lack", "back"]
) == 0  # identical suffixes

assert sol.distinctNames(
    ["a", "b"]
) == 2  # single-character strings

assert sol.distinctNames(
    ["ab", "cd"]
) == 2  # both swaps valid

assert sol.distinctNames(
    ["aa", "ba", "ca"]
) == 0  # all share same suffix

assert sol.distinctNames(
    ["apple", "banana", "cherry"]
) == 6  # every ordered pair valid

assert sol.distinctNames(
    ["coffee", "toffee"]
) == 0  # swapping recreates existing words

assert sol.distinctNames(
    ["aaa", "baa", "cbb"]
) == 4  # partial overlap

assert sol.distinctNames(
    ["ax", "bx", "cy"]
) == 4  # one shared suffix blocks some swaps

assert sol.distinctNames(
    ["abc", "def", "ghi", "jkl"]
) == 12  # all combinations valid

Test Summary

Test	Why
`["coffee","donuts","time","toffee"]`	Validates official example
`["lack","back"]`	Tests shared suffix invalidation
`["a","b"]`	Tests single-character strings
`["ab","cd"]`	Simple valid swap case
`["aa","ba","ca"]`	All suffixes overlap
`["apple","banana","cherry"]`	All swaps valid
`["coffee","toffee"]`	Swapping recreates originals
`["aaa","baa","cbb"]`	Mixed overlap scenario
`["ax","bx","cy"]`	Partial blocking due to shared suffix
`["abc","def","ghi","jkl"]`	Large fully valid combination set

Edge Cases

One important edge case is when multiple words share the same suffix. For example:

["lack", "back", "hack"]

All three words share "ack" as the suffix. Swapping first letters simply recreates existing words, so every swap is invalid. A naive implementation might accidentally count these as valid unless it explicitly checks suffix overlap. The set-intersection logic handles this naturally because shared suffixes are removed from consideration.

Another important edge case involves single-character strings such as:

["a", "b"]

The suffix for both words is the empty string "". Swapping first letters recreates the same words, which already exist. The implementation correctly stores empty suffixes and treats them like any other suffix, preventing incorrect counting.

A third edge case occurs when nearly every swap is valid. For example:

["abc", "def", "ghi", "jkl"]

All suffixes are unique, so every pair contributes fully. This can produce large answers, especially near the upper constraint limit. The Go implementation uses int64 to avoid integer overflow, while Python integers automatically expand as needed.