CODEWITHSUNDEEP
c
user10821869
user10821869

Reputation:

Is there a way if string repeats to return only repeated letters once?

I made code which will for string "aabbcc" return "abc" but in cases when there is more letters like "aaa" it will return "aa" instead of just one.

Here is the code I made.

void Ponavljanje(char *s, char *p) {
  int i, j = 0, k = 0, br = 0, m = 0;
  for (i = 0; i < strlen(s) - 1; i++) {
    for (j = i + 1; j < strlen(s); j++) {
      if (s[i] == s[j]) {
        br++;
        if (br == 1) {
          p[k++] = s[i];
        }
      }

    }
    br = 0;
  }
  p[k] = '\0';
  puts(p);
}

For "112233" output should be "123" or for "11122333" it should be also "123".

Upvotes: 0

Views: 171

Answers (5)

bruno
bruno

Reputation: 32596

does the work with a complexity O(n) I suppose programming can give rmg

void Ponavljanje(char *s,char *p)
{
  char n[256] = {0};
  int i = 0;

  while (*s) {
    switch (n[(unsigned char) *s]) {
    case 0:
      n[(unsigned char) *s] = 1;
      break;
    case 1:
      p[i++] = *s;
      n[(unsigned char) *s] = 2;
    }    
    s += 1;
  }

  p[i] = 0;

  puts(p);
}

Upvotes: 1

chux
chux

Reputation: 154315

  • Avoid repeated calls to strlen(s). A weak compiler may not see that s is unchanged and call strlen(s) many times, each call insuring a cost of n operations - quite inefficient. @arkku.1 Instead simply stop iterating when the null character detected.

  • Initialize a boolean list of flags for all char to false. When a character occurs, set the flag to prevent subsequent usage. Be careful when indexing that list as char can be negative.

  • Using a const char *s allows for wider allocation and helps a compiler optimization.

Example:

#include <stdbool.h>
#include <limits.h>

void Ponavljanje(const char *s, char *p) {
  const char *p_original = p;
  bool occurred[CHAR_MAX - CHAR_MIN + 1] = { 0 }; // all values set to 0 (false)
  while (*s) {
    if (!occurred[*s - CHAR_MIN]) {
      occurred[*s - CHAR_MIN] = true;
      *p++ = *s;
    }
    s++; 
  }
  *p = '\0';
  puts(p_original);
}

1 @wrongway4you comments that many compilers may assume the string did not change and optimize out the repeated strlen() call. A compliant compiler cannot do that though without restrict unless it is known that in all calls, s and p do not overlap. A compiler otherwise needs to assume p may affect s and warrant a repeated strlen() call.

Upvotes: 1

Craig Estey
Craig Estey

Reputation: 33621

Here is something that works regardless of order:

#include <stdio.h>
#include <string.h>

void
repeat(char *s, char *p)
{
    int slen;
    int sidx;
    int pidx;
    int plen;
    int schr;

    slen = strlen(s);
    plen = 0;

    for (sidx = 0; sidx < slen; ++sidx) {
        schr = s[sidx];

        // look for duplicate char
        int dupflg = 0;
        for (pidx = 0;  pidx < plen;  ++pidx) {
            if (p[pidx] == schr) {
                dupflg = 1;
                break;
            }
        }

        // skip duplicate chars
        if (dupflg)
            continue;

        p[plen++] = schr;
    }

    p[plen] = 0;

    puts(p);
}

int
main(void)
{
    char p[100];

    repeat("112233",p);
    repeat("123123",p);

    return 0;
}

Note: As others have mentioned, strlen should not be placed in the loop condition clause of the for [because the length of s is invariant]. Save strlen(s) to a separate variable and loop to that limit

Here is a different/faster version that uses a histogram so that only a single loop is required:

#include <stdio.h>
#include <string.h>

void
repeat(char *s, char *p)
{
    char dups[256] = { 0 };
    int slen;
    int sidx;
    int pidx;
    int plen;
    int schr;

    slen = strlen(s);

    sidx = 0;
    plen = 0;

    for (sidx = 0; sidx < slen; ++sidx) {
        schr = s[sidx] & 0xFF;

        // look for duplicate char
        if (dups[schr])
            continue;
        dups[schr] = 1;

        p[plen++] = schr;
    }

    p[plen] = 0;

    puts(p);
}

int
main(void)
{
    char p[100];

    repeat("112233",p);
    repeat("123123",p);

    return 0;
}

UPDATE #2:

I would suggest iterating until the terminating NUL byte

Okay, here's a full pointer version that is as fast as I know how to make it:

#include <stdio.h>
#include <string.h>

void
repeat(char *s, char *p)
{
    char dups[256] = { 0 };
    char *pp;
    int schr;

    pp = p;

    for (schr = *s++;  schr != 0;  schr = *s++) {
        schr &= 0xFF;

        // look for duplicate char
        if (dups[schr])
            continue;
        dups[schr] = 1;

        *pp++ = schr;
    }

    *pp = 0;

    puts(p);
}

int
main(void)
{
    char p[100];

    repeat("112233",p);
    repeat("123123",p);

    return 0;
}

Upvotes: 0

Tom Kuschel
Tom Kuschel

Reputation: 765

If you only want to remove the successive double letters, then this function would be sufficient, and the examples given in the question would fit:

#include <stdio.h>
void Ponavljanje(char *s,char *p)
{
  char dd = '\0';
  char *r;
  if(s == NULL || p == NULL)
    return;
  r = p;
  while(*s){
    if(*s != dd){
      *r = *s;
      dd = *s;
      r++;
    }
    s++;
  }
  *r = '\0';
  puts(p);
}
int main(void)
{
  char s[20] = "1111332222";
  char p[20];
  Ponavljanje(s,p);
}

Upvotes: 0

Arkku
Arkku

Reputation: 42149

While the inner loop checks br to only copy the output on the first repetition, the outer loop still passes over each repetition in s on future iterations. Hence each further occurrence of the same character will run a separate inner loop after br has already been reset.

With aaa as the input, both the first and the second a cause the inner loop to find a repetition, giving you aa. In fact, you always get one occurrence fewer of each character in the output than there is in the input, which means it only works for 1 or 2 occurrences in the input (resulting in 0 and 1 occurrences, respectively, in the output).

Upvotes: 0

Related Questions