C program to remove repeated char from a string

Question

I came across a interview question that asked to remove the repeated char from a given string, in-place. So if the input was "hi there" the output expected was "hi ter". It was also told to consider only alphabetic repititions and all the alphabets were lower case. I came up with the following program. I have comments to make my logic clear. But the program does not work as expectd for some inputs. If the input is "hii" it works, but if its "hi 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;

}

Have you made a typo in the expected output; should it not be either "hi there" -> "hi ter" or "Hi there" -> "Hi ther"? — Christoffer
– Christoffer, Commented Feb 11, 2010 at 11:33
That one functions is an associative array, but definitely not a hash table. — kennytm
– kennytm, Commented Feb 11, 2010 at 12:04

codaddict · Accepted Answer · 2010-02-11 11:31:28Z

11

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

hash[str[i] - 'a']

your program can blow.

ASCII value of space is 32 and that of a is 97 so you are effectively accessing array hash with a negative index.

To solve this you can ignore non-alphabets by doing :

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

answered Feb 11, 2010 at 11:31

codaddict

457k83 gold badges501 silver badges537 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Douglas Leeder Over a year ago

You might need to actually do an explicit check for lower case only as well?

Paul R · Accepted Answer · 2010-02-11 11:31:58Z

2

This is going to break on any space characters (or anything else outside the range 'a'..'z') because you are accessing beyond the bounds of your hash array.

answered Feb 11, 2010 at 11:31

Paul R

214k38 gold badges402 silver badges579 bronze badges

Comments

jim · Accepted Answer · 2010-02-11 12:54:25Z

2

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';
}

answered Feb 11, 2010 at 12:54

jim

211 bronze badge

Comments

4 revs · Accepted Answer · 2010-02-12 13:44:32Z

2

This is code golf, right?

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

edited Feb 12, 2010 at 13:44

community wiki

4 revs
finnw

1 Comment

t0mm13b Over a year ago

You should post that to IOCCC... ;)

tur1ng · Accepted Answer · 2010-02-11 11:33:38Z

1

...

// 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'])
    {

...

answered Feb 11, 2010 at 11:33

tur1ng

3,3395 gold badges28 silver badges32 bronze badges

1 Comment

gameover Over a year ago

If there is a non-alphabet other than space, say like a '?', this will fail again.

Vijay Mathew · Accepted Answer · 2010-02-11 12:07:52Z

1

#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');
}

answered Feb 11, 2010 at 12:07

Vijay Mathew

27.3k4 gold badges66 silver badges95 bronze badges

1 Comment

unwind Over a year ago

Two things: in_valid_range() is just islower(), so can be removed for brevity; get_hash_code() (and all treatments of hash codes) should be unsigned, since 'char' might not be, thus (int) (c - 'a') can be negative.

Phil Wallach · Accepted Answer · 2010-02-11 12:09:47Z

1

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++;
        }
    }
}

answered Feb 11, 2010 at 12:09

Phil Wallach

3,29322 silver badges19 bronze badges

Collectives™ on Stack Overflow

C program to remove repeated char from a string

7 Answers 7

1 Comment

Comments

Comments

1 Comment

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

1 Comment

Comments

Comments

1 Comment

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related