2306. Naming a Company

HardBit ManipulationArrayHash TableStringEnumeration
Leetcode Link

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 jth letter of the alphabet and do not exist in the original list ideas, given that we swap the first letter with the ith letter of the alphabet.

Approach to the solution:

  1. Create a set s from the list ideas for constant-time lookups to see if a string is part of the original list.
  2. Initialize a 2D list f with dimensions 26x26 to zero, which represents all possible swaps between letters.
  3. For each idea, compute the index of its first letter i (0 for 'a', 1 for 'b', etc.). Then for each possible first letter j (also 0-25), check if swapping the first letter of the idea with letter j results in a string not in the set s. If it isn't, increment f[i][j] by one. This tells us how many valid swaps we can make when the first letter of the original word is letter i and we swap it with letter j.
  4. After filling the 2D list f, we iterate again through each idea. For each idea, we look at the potential first letter after swapping i with every other letter j. We use our pre-computed f[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 set s, 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.
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Solution Approach

The implementation of the solution approach is as follows:

  1. Creating a Set for Fast Lookups: A set s is created from the input list ideas. Sets in Python provide O(1) average time complexity for lookups, which is crucial for checking if the swapped names already exist.
1s = set(ideas)
  1. 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.
1f = [[0] * 26 for _ in range(26)]
  1. 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 in s. If it's not, we increment f[i][j] by one.
1for v in ideas:
2    i = ord(v[0]) - ord('a')
3    t = list(v)
4    for j in range(26):
5        t[0] = chr(ord('a') + j)
6        if ''.join(t) not in s:
7            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.

  1. 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 of f[j][i] to a counter ans. This represents all the valid unique company names that can be formed by swapping the first character of idea with the jth character of the alphabet.
1ans = 0
2for v in ideas:
3    i = ord(v[0]) - ord('a')
4    t = list(v)
5    for j in range(26):
6        t[0] = chr(ord('a') + j)
7        if ''.join(t) not in s:
8            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).

  1. Return the Result: Lastly, we return ans, which by now holds the count of all distinct valid company names.
1return 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example 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:

1ideas = ["alpha", "bravo", "charlie", "delta"]
  1. Creating a Set for Fast Lookups: First, we create a set s from ideas:

    1s = set(["alpha", "bravo", "charlie", "delta"])
  2. 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.

    1f = [[0] * 26 for _ in range(26)]
  3. Populating the 2D List: Populating f involves iterating through ideas. Take "alpha" as an example: Its first letter index i is 0 ('a' - 'a'). For every other alphabet letter index j from 0 to 25, we try to swap 'a' with the jth letter: When j is 1 (which corresponds to 'b'), the swapped idea is "blpha" which isn't in set s. So, f[0][1] is incremented. This process is repeated for all ideas and for all characters in the alphabet.

  4. Counting Valid Names: With f populated, we now count valid company names. Go through each idea again; for "alpha": Index i is 0 ('a' - 'a'). For every possible other first letter j (i.e., 'b' to 'z'), we perform swaps and if the new name is not in s, we add the pre-computed value f[j][i] to our answer ans.

    For "alpha", swapping 'a' with 'b' would look at f[1][0] to see how many strings not in s can become "alpha" by swapping 'b' to 'a'. Since "blpha" is not in s, we have at least one valid pair: "blpha alpha".

  5. 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 say ans equals 6 (which is for illustration; the actual count will depend on the content of f 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
Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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 is O(n). Inside this loop, it runs another loop 26 times (for each letter in the alphabet), which brings this part to O(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 is O(26 * 26) which is a constant time operation, hence considered O(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 performs O(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 is O(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's O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫