Saturday, August 18, 2012

Determine if a string has all unique characters

Solution #1: 
The most simple approach will be to check each character with every other character. The time complexity will be O(n^2) with no extra space requirement.

Solution #2:
If changes are allowed, then we can sort the string in O(n log n) time and then check the adjacent elements for duplicates. Total time complexity is n log n + n ==> n log n.

Solution #3: 
If the string is formed of extended ASCII characters then we can make an array of size 256 and store the occurrence of each character in this array.

int main(int argc, char** argv)
{
    int arr[256] = {0,};
    char *ptr = NULL;

    ptr = argv[1];

    while(*ptr != '\0')
    {
        if(arr[*ptr])
        {
            printf("Found Duplicate...\n");
            return 0;
        }
        else
        {
            arr[*ptr] = 1;
        }
        ptr++;
    }

    printf("No duplicates...\n");

    return 1;
}

No comments:

Post a Comment