aboutsummaryrefslogtreecommitdiff
path: root/string_compression.c
blob: 37490e27623c592d7336a03253239e1c31de3516 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 443. String Compression
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * given array of characters 'chars', compress it using following
 * algorithm: being with empty string 's'. for each group of
 * consecutive repeating characters in 'chars': if the group's
 * length is 1, append character to 's'. otherwise, append character
 * followed by the group's length. the compressed string 's' should
 * not be returned separately, but instead, be stored in input
 * character array 'chars'. note that group lengths are 10 or longer
 * will be split into multiple characters in 'chars'. return new
 * length of array. algorithm must be contant space complexity
 */

char *int2char(int n) {
  char *res = malloc(11);
  res[10] = '\0'; // null terminate
  int idx = 9;
  while (n) {
    res[idx] = '0' + n % 10;
    n /= 10;
    idx--;
  }
  return &res[idx + 1];
}

int compress(char *chars, int charsSize) {
  int idx = 0, cnt = 1;
  char target = chars[0];
  for (int i = 1; i < charsSize; i++) {
    if (chars[i] == chars[i - 1])
      cnt++;
    else {
      chars[idx] = target;
      idx++;
      if (cnt > 1) {
        char *tmp = int2char(cnt);
        strncpy(&chars[idx], tmp, strlen(tmp));
        idx += strlen(tmp);
      }
      cnt = 1;
      target = chars[i];
    }
  }
  chars[idx] = target;
  idx++;
  if (cnt > 1) {
    char *tmp = int2char(cnt);
    strncpy(&chars[idx], tmp, strlen(tmp));
    idx += strlen(tmp);
  }
  return idx;
}

int main() {
  char c1[] = {'a', 'a', 'b', 'b', 'c', 'c', 'c'};
  char c2[] = {'a'};
  char c3[] = {'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'};
  printf("%d\n", compress(c1, 7));  // expect: ["a","2","b","2","c","3"]
  printf("%d\n", compress(c2, 1));  // expect: ["a"]
  printf("%d\n", compress(c3, 13)); // expect: ["a","b","1","2"]
}