Sunday, February 23, 2014

Remove the duplicate elements in the string

Given a string, inplace remove the duplicate elements form the string.
For e.g. the given string is "codersstop is  a programming blog"
Result: "coderstp iagmnbl"


Maintain a lookup table of the 256 entries to mark the occurrence of each of the characters, and only copy the elements which are occurring for the first time.
Below snippet of code removes the duplicate elements from the string

void removeDuplicate(char * s) {
    char a[256] = {0}, c = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++) {
        if(a[s[i]] == 0) s[c++] = s[i];
        a[s[i]] = 1;
    s[c] = '\0';

Overall time complexity is O(n) and space complexity O(1)

No comments :

Post a Comment