2306. Naming a Company
Problem Description
The given problem presents a creative challenge of naming a company by generating names from a list of string ideas. The procedure to create a company name is quite unique. We must take two distinct names from the ideas
list, which we will refer to as ideaA
and ideaB
. Then we swap the first letters of each idea. After swapping, we need to check if the new names, obtained after swapping the first characters, do not already exist in the original ideas
list. If they do not exist, the concatenation of ideaA
and ideaB
separated by a space creates a valid company name. The main task is to count how many distinct valid company names can be produced following these rules.
Intuition
The primary insight in solving this problem lies in the realization that direct computation for each pair would be inefficient due to the sheer potential number of pairs; for n
ideas, there are O(n^2)
pairs to consider.
Hence, the solution employs a clever technique to reduce the complexity of the problem. It uses a two-dimensional list f
, where f[i][j]
keeps a count of how many strings we can form that have their first letter as the j
th letter of the alphabet and do not exist in the original list ideas
, given that we swap the first letter with the i
th letter of the alphabet.
Approach to the solution:
- Create a set
s
from the listideas
for constant-time lookups to see if a string is part of the original list. - Initialize a 2D list
f
with dimensions 26x26 to zero, which represents all possible swaps between letters. - For each idea, compute the index of its first letter
i
(0 for 'a', 1 for 'b', etc.). Then for each possible first letterj
(also 0-25), check if swapping the first letter of the idea with letterj
results in a string not in the sets
. If it isn't, incrementf[i][j]
by one. This tells us how many valid swaps we can make when the first letter of the original word is letteri
and we swap it with letterj
. - After filling the 2D list
f
, we iterate again through each idea. For each idea, we look at the potential first letter after swappingi
with every other letterj
. We use our pre-computedf[j][i]
values to add to the total count of valid company names. This is possible because if swapping the first letter of one idea does not result in a collision with the original sets
, then all the other names that can be formed by replacing their first letter with the current idea's first letter (and also not resulting in a collision) can form a valid company name pair with the current idea. - Return the final count of valid company names.
The solution is efficient because it transforms the problem into a counting problem that avoids considering every pair individually by precomputing possible valid swap counts.
Solution Approach
The implementation of the solution approach is as follows:
- Creating a Set for Fast Lookups: A set
s
is created from the input listideas
. Sets in Python provide O(1) average time complexity for lookups, which is crucial for checking if the swapped names already exist.
s = set(ideas)
- Initializing a 2D List for Swap Counts: A 2D list
f
with dimensions 26x26 is initialized to zero. This list will store counts of possible swaps for every pair of letters in the alphabet.
f = [[0] * 26 for _ in range(26)]
- Populating the 2D List: For each idea, we determine the index of its first letter in the alphabet (
i
). Then, for each alphabet letter (j
), we construct a new string by swapping the first letter and check if it's not ins
. If it's not, we incrementf[i][j]
by one.
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
This step uses two key Python functions: ord()
to obtain the ASCII value of a character, and chr()
to convert an ASCII value back to a character.
- Counting Valid Names: We iterate through each idea again. This time, for every possible swap that results in a name not in
s
, we add the pre-computed value off[j][i]
to a counterans
. This represents all the valid unique company names that can be formed by swapping the first character ofidea
with thej
th character of the alphabet.
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]
This works under the premise that if swapping ideaA
's first letter with ideaB
's first letter results in a string that does not collide with the original list, then ideaB
can form a valid pair with all ideaA
-like strings (strings that would be formed by making the same letter-swap on ideaA
's first letter).
- Return the Result: Lastly, we return
ans
, which by now holds the count of all distinct valid company names.
return ans
This approach encapsulates an efficient way to compute the number of distinct valid names by using a combination of (a) a hash set for fast string existence checks, (b) a 2D count array to avoid redundant checks, and (c) optimized iteration over the ideas
list and the English alphabet to leverage those structures.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the approach.
Assume we have the following list of string ideas for our company naming task:
ideas = ["alpha", "bravo", "charlie", "delta"]
-
Creating a Set for Fast Lookups: First, we create a set
s
fromideas
:s = set(["alpha", "bravo", "charlie", "delta"])
-
Initializing a 2D List for Swap Counts: We initialize a 2D list
f
with dimensions 26x26 to zero. This will store counts of possible name swaps for every pair of letters.f = [[0] * 26 for _ in range(26)]
-
Populating the 2D List: Populating
f
involves iterating throughideas
. Take "alpha" as an example: Its first letter indexi
is 0 ('a' - 'a'). For every other alphabet letter indexj
from 0 to 25, we try to swap 'a' with thej
th letter: Whenj
is 1 (which corresponds to 'b'), the swapped idea is "blpha" which isn't in sets
. So,f[0][1]
is incremented. This process is repeated for all ideas and for all characters in the alphabet. -
Counting Valid Names: With
f
populated, we now count valid company names. Go through each idea again; for "alpha": Indexi
is 0 ('a' - 'a'). For every possible other first letterj
(i.e., 'b' to 'z'), we perform swaps and if the new name is not ins
, we add the pre-computed valuef[j][i]
to our answerans
.For "alpha", swapping 'a' with 'b' would look at
f[1][0]
to see how many strings not ins
can become "alpha" by swapping 'b' to 'a'. Since "blpha" is not ins
, we have at least one valid pair: "blpha alpha". -
Return the Result: After iterating through all ideas and all possible first letters,
ans
will be the total count of valid company name pairs. For this example, let's sayans
equals 6 (which is for illustration; the actual count will depend on the content off
after computing).
The takeaway from the illustration is we avoid checking all possible pairs directly by instead preparing a lookup that tells us potential valid pairs and using that to count efficiently.
Solution Implementation
1class Solution:
2 def distinctNames(self, ideas: List[str]) -> int:
3 # Convert list of ideas to a set for fast lookups
4 ideas_set = set(ideas)
5
6 # Initialize a 26x26 grid to keep count of possible distinct names
7 counts = [[0] * 26 for _ in range(26)]
8
9 # First pass: count possible prefixes for each alphabet character
10 for idea in ideas:
11 first_letter_index = ord(idea[0]) - ord('a')
12 for j in range(26):
13 # Change the first character and check if it forms a new idea
14 new_first_char = chr(ord('a') + j)
15 new_idea = new_first_char + idea[1:]
16 if new_idea not in ideas_set:
17 counts[first_letter_index][j] += 1
18
19 # Initialize variable for the final answer
20 result = 0
21
22 # Second pass: calculate the number of distinct names
23 for idea in ideas:
24 first_letter_index = ord(idea[0]) - ord('a')
25 for j in range(26):
26 # Change the first character and check if it forms a new idea
27 new_first_char = chr(ord('a') + j)
28 new_idea = new_first_char + idea[1:]
29 if new_idea not in ideas_set:
30 # Increment the result by the precalculated count of possible
31 # distinct names that start with the new first character
32 result += counts[j][first_letter_index]
33
34 # Return the total number of distinct name combinations
35 return result
36
1class Solution {
2 // Function to find the number of distinct pairs of strings
3 // that result in distinct strings when their first letters are swapped.
4 public long distinctNames(String[] ideas) {
5 // Create a set to store all unique ideas.
6 Set<String> uniqueIdeas = new HashSet<>();
7 for (String idea : ideas) {
8 uniqueIdeas.add(idea);
9 }
10
11 // 2D array to store frequency of possible swaps that result in a distinct name.
12 int[][] frequency = new int[26][26];
13
14 // Populate the frequencies of valid swaps.
15 for (String idea : ideas) {
16 char[] characters = idea.toCharArray();
17 int firstCharIndex = characters[0] - 'a';
18
19 // Check all possible first letters swaps for the current idea.
20 for (int newFirstCharIndex = 0; newFirstCharIndex < 26; ++newFirstCharIndex) {
21 characters[0] = (char) (newFirstCharIndex + 'a');
22
23 // If the new string created with the swapped first character
24 // is not present in the uniqueIdeas set, increment the count.
25 if (!uniqueIdeas.contains(String.valueOf(characters))) {
26 ++frequency[firstCharIndex][newFirstCharIndex];
27 }
28 }
29 }
30
31 // Count the number of distinct pairs by analyzing swaps from different starting characters.
32 long distinctPairsCount = 0;
33 for (String idea : ideas) {
34 char[] characters = idea.toCharArray();
35 int originalFirstCharIndex = characters[0] - 'a';
36
37 // Count valid pairs by trying every first letter swap.
38 for (int newFirstCharIndex = 0; newFirstCharIndex < 26; ++newFirstCharIndex) {
39 characters[0] = (char) (newFirstCharIndex + 'a');
40
41 // If the swap results in a distinct name that's not in the set,
42 // add the frequency of the opposite swap (j, i) to the count.
43 if (!uniqueIdeas.contains(String.valueOf(characters))) {
44 distinctPairsCount += frequency[newFirstCharIndex][originalFirstCharIndex];
45 }
46 }
47 }
48
49 // Return the computed number of distinct pairs.
50 return distinctPairsCount;
51 }
52}
53
1#include <vector>
2#include <string>
3#include <unordered_set>
4
5class Solution {
6public:
7 long long distinctNames(vector<string>& ideas) {
8 // We use a set to store all ideas for constant time look-up
9 unordered_set<string> ideasSet(ideas.begin(), ideas.end());
10
11 // Create a 26x26 matrix to store counts of transformations
12 // that result in a valid distinct name (not present in set)
13 vector<vector<int>> transformationCount(26, vector<int>(26));
14
15 // Iterate through each idea to calculate possible transformations
16 for (auto& idea : ideas) {
17 int initialCharIndex = idea[0] - 'a';
18 for (int charOffset = 0; charOffset < 26; ++charOffset) {
19 // Change the first character of the idea
20 idea[0] = charOffset + 'a';
21
22 // If the transformed idea is not in the set, increment the count
23 if (!ideasSet.count(idea)) {
24 ++transformationCount[initialCharIndex][charOffset];
25 }
26 }
27 // Reset the first character of the idea after checking
28 idea[0] = initialCharIndex + 'a';
29 }
30
31 // Initialize answer to store the total count of distinct names
32 long long answer = 0;
33
34 // Iterate through the ideas again to calculate distinct names
35 for (auto& idea : ideas) {
36 int initialCharIndex = idea[0] - 'a';
37 for (int charOffset = 0; charOffset < 26; ++charOffset) {
38 // Change the first character of the idea
39 idea[0] = charOffset + 'a';
40
41 // Check if the transformed idea is not present in the set which means
42 // it's distinct and add to answer the number of ways the transformation
43 // from the other characters to the current initial character can be done
44 if (!ideasSet.count(idea)) {
45 answer += transformationCount[charOffset][initialCharIndex];
46 }
47 }
48 // Reset the first character of the idea after checking
49 idea[0] = initialCharIndex + 'a';
50 }
51
52 // Return the total count of distinct names that could be created
53 return answer;
54 }
55};
56
1// Importing Set type from 'typescript-collections' package for similar set functionality as in C++.
2// Note: TypeScript has a built-in Set, but 'typescript-collections' may offer a closer experience to C++'s std::unordered_set
3import { Set } from 'typescript-collections';
4
5// Helper type to represent a 2D array (matrix)
6type Matrix = number[][];
7
8// Function to calculate the distinct names
9function distinctNames(ideas: string[]): number {
10 // Create a Set to store all ideas for constant time look-up
11 let ideasSet: Set<string> = new Set<string>();
12 ideas.forEach((idea) => ideasSet.add(idea));
13
14 // Create a 26x26 matrix to store counts of transformations
15 // that result in a valid distinct name (not present in set)
16 let transformationCount: Matrix = new Array(26);
17 for (let i = 0; i < 26; i++) {
18 transformationCount[i] = new Array(26).fill(0);
19 }
20
21 // Iterate through each idea to calculate possible transformations
22 ideas.forEach((idea) => {
23 let initialCharIndex: number = idea.charCodeAt(0) - 'a'.charCodeAt(0);
24 for (let charOffset = 0; charOffset < 26; charOffset++) {
25 // Change the first character of the idea
26 let transformedIdea: string = String.fromCharCode(charOffset + 'a'.charCodeAt(0)) + idea.slice(1);
27
28 // If the transformed idea is not in the set, increment the count
29 if (!ideasSet.contains(transformedIdea)) {
30 transformationCount[initialCharIndex][charOffset]++;
31 }
32 }
33 });
34
35 // Initialize answer to store the total count of distinct names
36 let answer: number = 0;
37
38 // Iterate through the ideas again to calculate distinct names
39 ideas.forEach((idea) => {
40 let initialCharIndex: number = idea.charCodeAt(0) - 'a'.charCodeAt(0);
41 for (let charOffset = 0; charOffset < 26; charOffset++) {
42 // Change the first character of the idea
43 let transformedIdea: string = String.fromCharCode(charOffset + 'a'.charCodeAt(0)) + idea.slice(1);
44
45 // Check if the transformed idea is not present in the set which means
46 // it's distinct and adds to the answer the number of ways the transformation
47 // from the other characters to the current initial character can be done
48 if (!ideasSet.contains(transformedIdea)) {
49 answer += transformationCount[charOffset][initialCharIndex];
50 }
51 }
52 });
53
54 // Return the total count of distinct names that could be created
55 return answer;
56}
57
Time and Space Complexity
The given Python script is designed to find the number of distinct pairs of names that can be formed by switching the first letters of two different strings from a provided list, provided that the new strings do not appear in the original list.
Time Complexity
The time complexity of the above code is O(n * k + 26 * 26)
where n
is the number of ideas (strings) in the input ideas
list, and k
is the average length of the ideas.
- The first
for
loop runs through all the given ideas which isO(n)
. Inside this loop, it runs another loop 26 times (for each letter in the alphabet), which brings this part toO(n * 26)
. - In the nested loop, it constructs a new string which is
O(k)
operation as it depends on the length of the word. - The construction of
f
using two lists (each of size 26) for counting isO(26 * 26)
which is a constant time operation, hence consideredO(1)
in the overall complexity.
Therefore, the first portion of code dealing with populating f
is O(n * k)
.
-
The second for-loop is similar to the first part, running for each idea
n
and internally iterating 26 times to try out each alphabet, also creating a new string every time. So it performsO(n * k)
operations as well. -
The increment operation inside the second loop is
O(1)
. After the nested loops, it sums up the computed values, which isO(26 * 26)
since we are iterating over all possible pairs of letters.
This results in the second for-loop also having a complexity of O(n * k)
.
Since O(n * k)
dominates over O(26 * 26)
, the total time complexity of the script is O(n * k)
.
Space Complexity
The space complexity of the code is O(n + 26 * 26)
.
- We have a set
s
that is storing all the ideas, so in the worst case, it'sO(n)
for space. - The list
f
is a 2D list with 26 * 26 integers since we have 26 possible starting letters and we are counting possibilities for each pair.
As O(n)
dominates over O(26 * 26)
, the overall space complexity is O(n)
which is based on the number of unique ideas in the input list.
In summary, the code provided is quite efficient, with linear time complexity depending on the number of input strings and their average length, and also linear space complexity depending on just the number of input strings.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!