Find if all characters are unique in string

I found this problem in ‘Cracking the Code Interview’ book. It’s actually the first problem given (1.1) in the book. It is a pretty common question asked in interviews. The problem is about writing a function that returns true if all characters in string are unique, and false otherwise. There is actually a lot more to it that it may look like first. I implemented a few solutions in C.


#define FALSE 0
#define TRUE 1

/* implement function that returns true
is all characters in a string are
unique, and false otherwise
*/

// time O(n^2). No extra space needed
int uniqueCharac1(char *ptr1) {
    char *ptr2;
    while (*ptr1++ != '\0') {
        ptr2 = ptr1;
        while (*ptr2++ != '\0') {
            if (*ptr2 == *ptr1) {
                printf("Letter %c repeated\n", *ptr2);
                return FALSE;
            }
        }
    }
    return TRUE;
}

//time O(n). Extra space O(1). Using bitmap
int uniqueCharac2(char *ptr) {
    unsigned int bit_field = 0x0; // needs 27 bits (one bit per letter).
    // int gives 4 bytes (32 bits)
    int character;
    while (*ptr++ != '\0') {
        character = *ptr - 'a' + 1; // 'a' is 1
        //printf("Letter %c is number %d\n", *ptr, character);
        // checking if bit set
        if (bit_field && (1<<character)) {
            printf("Letter %c repeated\n", *ptr);
            return FALSE;
        }
        // setting bit
        bit_field |= (1&lt;&lt;character);
    }
    return TRUE;
}

char * quicksort(char *string) { // TO DO
    return string;
}
int binarysearch(char *string, char letter) { // TO DO
    return TRUE;
}

//time O(n*log n). No extra space needed. Using quicksort
int uniqueCharac3(char *ptr) {
    char *sorted = quicksort(ptr);
    while (*ptr++ != '') {
        if (binarysearch(ptr + 1, *ptr)) {
            printf("Letter %c repeated\n", *ptr);
            return TRUE;
        }
    }
    return FALSE;
}

int main(int argc, char **argv){
    char string[] = "asdfqwersdfga";
    if (uniqueCharac1(string)) {printf("Characters in %s are unique\n", string); }
    if (uniqueCharac2(string)) {printf("Characters in %s are unique\n", string); }

}


Leave a comment