Sponsored
Sponsored
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.
Time Complexity: O(n^2 * m), where n is the number of ideas, and m is the average length of the ideas, due to the nested loop and string comparison.
Space Complexity: O(1) as we are not using any additional space proportional to input size beyond function parameters.
1import java.util.*;
2
3public class NamingCompany {
4
5 public static boolean isValidName(StringBuilder a, StringBuilder b, Set<String> ideaSet) {
6 char temp = a.charAt(0);
7 a.setCharAt(0, b.charAt(0));
8 b.setCharAt(0, temp);
9
10 boolean valid = !ideaSet.contains(a.toString()) && !ideaSet.contains(b.toString());
11
12 // Swap back
13 a.setCharAt(0, temp);
14 b.setCharAt(0, a.charAt(0));
15
16 return valid;
17 }
18
19 public static int countValidNames(String[] ideas) {
20 int validNames = 0;
21 Set<String> ideaSet = new HashSet<>(Arrays.asList(ideas));
22 int ideasSize = ideas.length;
23
24 for (int i = 0; i < ideasSize; i++) {
25 for (int j = i + 1; j < ideasSize; j++) {
26 if (isValidName(new StringBuilder(ideas[i]), new StringBuilder(ideas[j]), ideaSet)) {
27 validNames++;
28 }
29 }
30 }
31
32 return validNames * 2; // Counting both (a,b) and (b,a)
33 }
34
35 public static void main(String[] args) {
36 String[] ideas = {"coffee", "donuts", "time", "toffee"};
37 System.out.println(countValidNames(ideas));
38 }
39}The Java solution converts strings into mutable StringBuilder objects to easily swap characters. It uses a HashSet for efficient membership testing and counts valid combinations based on name uniqueness.
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.
Time Complexity: O(n^2 * m) but more efficient than brute force due to reduced checking within grouped sets.
Space Complexity: O(n) since we store ideas organized by prefix.
1
Java implementation uses lists of sets categorized by first-character prefixes to reduce unnecessary pairing between incomparable prefixes. This refinement cuts computation significantly without compromising correctness.