Check for whether a string contains any duplicate characters

Question

I am a new programmer and I want to know if I'm inheriting the right styles. I don't want to pick up any bad/amateur habits. Any advice would be much appreciated.

This is an isUnique function I wrote in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{   
    int x;
    char s1[] = "dog hi cobe!";
    x = isUnique(s1);
    printf("%d", x);
    return 0;
}

isUnique(char* s1)
{
    char holder;
    int i;
    int j;

    if(s1 == NULL)
        return -1;

    for(i = 0; i < (strlen(s1) -1); i++)
    {
        holder = s1[i];
        for(j = i; j < (strlen(s1)-1); j++)
        {
            if(holder == s1[j+1])
            {
                if(holder == ' ')
                    continue;
                else
                    return 0;
            }
        }
    }
    return 1;
}

And I'm going to say the run time complexity is \$O(n^2)\$, would I be correct?

Answer 1

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]);
    }
}

Answer 2

The combination of conditions

        if(holder == s1[j+1])
        {
            if(holder == ' ')
                continue;

makes the whole inner loop void if holder == ' ', so you may save scanning the string much earlier:

for(i = 0; i < (strlen(s1) -1); i++)
{
    holder = s1[i];
    if(holder == ' ')
        continue;
    for(j = i; j < (strlen(s1)-1); j++)
    {
        if(holder == s1[j+1])
        {
            return 0;
        }
    }
}

Additionally you can simplify the code a bit if you start the j loop one char ahead:

int len = strlen(s1);
for(i = 0; i < len-1; i++)
{
    holder = s1[i];
    if(holder == ' ')
        continue;
    for(j = i+1; j < len; j++)
    {
        if(holder == s1[j])
        {
            return 0;
        }
    }
}

For such a relatvely small symbol set (256 possible values of char type, max 255 of which can appear in the string) you can just arrange an array of counters:

int counter[256];

reset it to zeros:

for(i = 0; i < 256; i++)
    counter[i] = 0;

or, based on the known array of int memory layout:

memset(counter, 0, 256*sizeof(int));

and count occurences of each character (up to two)

for(i = 0; i < strlen(s1); i++)
{
    if(s1[i] != ' ')
        if(++counter[(unsigned char)s1[i]] > 1)
        {
            return 0;
        }
}
return 1;

This will test your string in linear time (plus constant time for preparing counter[] array).

Answer 3

When compiling, always enable all the warnings.

(for gcc, at a minimum use: -Wall -Wextra -pedantic I also use -Wconversion -std=c99 )

the result will be:

1. implicit declaration of function: isUnique
2. return type defaults to 'int' for function: isUnique
3. comparison between signed and unsigned integer expressions for line: for(i = 0; i < (strlen(s1) -1); i++)
4. comparison between signed and unsigned integer expressions for line: for(j = i; j < (strlen(s1)-1); j++).
5. Note: strlen() returns size_t not int
6. there is no need to call strlen() at all! instead use something like: for(j = i; s1[j]; j++) which will exit the loop upon encountering the NUL string terminator byte.
7. when possible, data/variables should be localized to where they are used. so these lines can be eliminated: int i; int j; by writing the loop similar to: for(size_t j = i; s1[j]; j++)
8. there is no need for the char holder; line.
9. the 'j' variable is being started with j = i is should be j = i+1
10. Stopping the search because a space is encountered is not correct.
11. do not #include headers those contents are not being used.
12. use strategic comments so the reader, (and you in 6 months) will know what is being done in the code
13. always use function prototypes so the compiler will not be using some 'default' values/types (and in latest C standard, the defaults are changed thereby causing the compiler to raise warnings)

Here is a suggested implementation

#include <stdio.h>

// prototypes
int isUnique(char* s1);

int main( void )
{
    int x;
    char *s1 = "dog hi cobe!";
    x = isUnique(s1);
    printf("%d", x);
    return 0;
} // end function: main

int isUnique(char* s1)
{

    if( !s1 )
    { 
        // indicate no string passed
        return -1;
    }

    for( size_t i = 0; s1[i]; i++ )
    {
        for( size_t j = i+1; s1[j]; j++ )
        {
            if( s1[i] == s1[j] )
            { 
                // indicate characters are not unique
                return 0;
            }
        }
    }
    // indicate characters are unique
    return 1;
} // end function: isUnique