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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5int isValidName(char *a, char *b, char **ideas, int ideasCount) {
6 char temp;
7 temp = a[0];
8 a[0] = b[0];
9 b[0] = temp;
10
11 for (int i = 0; i < ideasCount; i++) {
12 if (strcmp(a, ideas[i]) == 0 || strcmp(b, ideas[i]) == 0) {
13 // Swap back and return false as they exist
14 temp = a[0];
15 a[0] = b[0];
16 b[0] = temp;
17 return 0;
18 }
19 }
20
21 // Swap back the first letter after checking
22 temp = a[0];
23 a[0] = b[0];
24 b[0] = temp;
25
26 return 1;
27}
28
29int countValidNames(char **ideas, int ideasSize) {
30 int validNames = 0;
31
32 for (int i = 0; i < ideasSize; i++) {
33 for (int j = i + 1; j < ideasSize; j++) {
34 if (isValidName(ideas[i], ideas[j], ideas, ideasSize)) {
35 validNames++;
36 }
37 }
38 }
39
40 return validNames * 2; // Since (a,b) and (b,a) both should be counted
41}
42
43int main() {
44 char *ideas[] = {"coffee", "donuts", "time", "toffee"};
45 int ideasSize = sizeof(ideas) / sizeof(ideas[0]);
46 printf("%d\n", countValidNames(ideas, ideasSize));
47 return 0;
48}This implementation iterates over each possible pair of ideas and attempts to swap their first letters. If the new names generated are not found among the original ideas, it counts such pairs as valid. It restores the original names after checking for existence.
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
This C solution organizes names by their starting letters and checks pairwise swapping between distinct prefix sets. By checking overlapping only within sets of the same initial character, it reduces redundant checks and improves efficiency over brute force.