Missing return type
This function declaration is missing the return type:
isUnique(char* s1)
Sure, the default return type is int
in C,
but it would be better to just write it anyway for clarity.
Use boolean
C99 has a bool
type with true
and false
values,
which you can get from this #include
:
#include <stdbool.h>
It would be better to rewrite isUnique
to return a bool
.
Even though, this will mean giving up the special value -1 for the NULL
input case. But that doesn't seem so bad. A name like "is*" is commonly expected to return a boolean. If you really need a function that can handle the NULL
case, you could create a wrapper function:
/* returns -1 on NULL input, 0 if not unique, 1 if unique */
int checkUnique(char* s1) {
if (s1 == NULL) return -1;
return isUnique(s1);
}
Note that the bool
return value of isUnique
will be converted to int
, so that false
is 0 and true
is 1.
Avoid repeated calculations
You call strlen(s1)
twice:
for(i = 0; i < (strlen(s1) -1); i++)
{
holder = s1[i];
for(j = i; j < (strlen(s1)-1); j++)
It would be better to call it once, store in a variable and reuse.
Time complexity
As you suspected, the time complexity of your algorithm is \$O(n^2)\$:
all characters are compared with all other.
You could improve that to \$O(n)\$ by using extra storage, the size of the alphabet.
You could create an array of bool
, representing if a character was already seen or not:
- All values are initialized to
false
- For character in the input, check if it was seen
- If it was seen, return
false
- If it was not seen, mark it now (set value in the
bool
array to true
)
- If the end of the string is reached, return
true
Something like this:
bool isUnique(char * string) {
int len = strlen(string);
bool seen[256];
memset(seen, false, sizeof(seen));
int i;
for (i = 0; i < len; i++) {
char c = string[i];
if (seen[c]) {
return false;
}
seen[c] = true;
}
return true;
}
Printing the result
This will print a 0 or 1:
int x;
char s1[] = "dog hi cobe!";
x = isUnique(s1);
printf("%d", x);
It would be more informative to print the strings that was tested, and "false"/"true" instead of 0/1:
char s1[] = "dog hi cobe!";
printf("%s -> %s\n", s1, isUnique(s1) ? "true" : "false");
Usability
It would be more interesting if the program took the strings from the command line, instead of using hardcoded values, for example:
void printWithResult(char* string) {
printf("%s -> %s\n", string, isUnique(string) ? "true" : "false");
}
int main(int argc, char ** argv) {
int i;
for (i = 1; i < argc; i++) {
printWithResult(argv[i]);
}
}