C to remove duplicate char from string

Question

I came across an interview question that asked to remove a duplicate char from a given string in place. Therefore, if the input was “hi there,” the expected result was “hi.” It was also said to consider only alphabetical repetitions and all alphabets were in lower case. I came up with the following program. I have comments to make my logic clear. But the program does not work as expected for some inputs. If the input "hii" works, but if its "hello there", it fails. Please, help.

#include <stdio.h> int main() { char str[] = "programming is really cool"; // original string. char hash[26] = {0}; // hash table. int i,j; // loop counter. // iterate through the input string char by char. for(i=0,j=0;str[i];) { // if the char is not hashed. if(!hash[str[i] - 'a']) { // hash it. hash[str[i] - 'a'] = 1; // copy the char at index i to index j. str[j++] = str[i++]; } else { // move to next char of the original string. // do not increment j, so that later we can over-write the repeated char. i++; } } // add a null char. str[j] = 0; // print it. printf("%s\n",str); // "progamin s ely c" expected. return 0; 

}

Answer 1

when str[i] is a non-alphabet, say a space and when you do:

 hash[str[i] - 'a'] 

Your program may explode.

The value of ASCII space is 32 , and the value of a is 97 , so you effectively access the hash of an array with a negative index.

To solve this problem, you can ignore non-alphabets by following these steps:

 if(! isalpha(str[i]) { str[j++] = str[i++]; // copy the char. continue; // ignore rest of the loop. } 

Answer 2

This breaks any whitespace (or anything else outside the range of "a" .. "z") because you are accessing outside of your hash array.

Answer 3

This is a golf code, right?

 d(s){char*i=s,*o=s;for(;*i;++i)!memchr(s,*i,os)?*o++=*i:0;*o=0;} 

Answer 4

 void striprepeatedchars(char *str) { int seen[UCHAR_MAX + 1]; char *c, *n; memset(seen, 0, sizeof(seen)); c = n = str; while (*n != '\0') { if (!isalpha(*n) || !seen[(unsigned char) *n]) { *c = *n; seen[(unsigned char) *n]++; c++; } n++; } *c = '\0'; } 

Answer 5

...

 // iterate through the input string char by char. for(i=0,j=0;str[i];) { if (str[i] == ' ') { str[j++] = str[i++]; continue; } // if the char is not hashed. if(!hash[str[i] - 'a']) { 

...

Answer 6

 #include <stdio.h> #include <string.h> int hash[26] = {0}; static int in_valid_range (char c); static int get_hash_code (char c); static char * remove_repeated_char (char *s) { size_t len = strlen (s); size_t i, j = 0; for (i = 0; i < len; ++i) { if (in_valid_range (s[i])) { int h = get_hash_code (s[i]); if (!hash[h]) { s[j++] = s[i]; hash[h] = 1; } } else { s[j++] = s[i]; } } s[j] = 0; return s; } int main (int argc, char **argv) { printf ("%s\n", remove_repeated_char (argv[1])); return 0; } static int in_valid_range (char c) { return (c >= 'a' && c <= 'z'); } static int get_hash_code (char c) { return (int) (c - 'a'); } 

Answer 7

 char *s; int i = 0; for (i = 0; s[i]; i++) { int j; int gap = 0; for (j = i + 1; s[j]; j++) { if (gap > 0) s[j] = s[j + gap]; if (!s[j]) break; while (s[i] == s[j]) { s[j] = s[j + gap + 1]; gap++; } } }