aboutsummaryrefslogtreecommitdiff
path: root/construct_string_repeat_lim.c
blob: 6f0f69cbb2179ec0a39e39b1c35e9e2b0a71303b (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
// 2182. Construct String With Repeat Limit
#include "leetcode.h"

/*
 * you are given a string 's' and an integer 'repeatLimit'. construct a new
 * string 'repeatLimitedString' using the characters of 's' such that no letter
 * appears more than 'repeatLimit' times in a row. you do not have to use all
 * characters from 's'. return the lexicographically largest
 * 'repeatLimitedString' possible. a string 'a' is lexicographically larger than
 * string 'b' if in the first position where 'a' and 'b' differ, string 'a' has
 * a letter that appears later in the alphabet than the corresponding letter  in
 * 'b'. if the first 'min(a.len, b.len)' characters do not differ, then the
 * longer string is the lexicographically larger one
 */

int *get_cnt(char *s) {
  int n = strlen(s);
  int *cnt = (int *)calloc(26, sizeof(int));
  for (int i = 0; i < n; i++)
    cnt[s[i] - 'a']++;
  return cnt;
}

char *repeatLimitedString(char *s, int repeatLimit) {
  int n = strlen(s), *cnt = get_cnt(s), idx = 0;
  char *ans = (char *)calloc(n + 1, sizeof(char));
  for (int i = 'z' - 'a'; i >= 0;) {
    if (!cnt[i]) {
      i--;
      continue;
    }
    char c = i + 'a';
    if (!idx || ans[idx - 1] != c) {
      int copy = cnt[i] <= repeatLimit ? cnt[i] : repeatLimit;
      memset(&ans[idx], c, copy);
      idx += copy;
      cnt[i] -= copy;
    } else {
      int next = i - 1;
      while (next >= 0 && !cnt[next])
        next--;
      if (next < 0)
        break;
      else {
        ans[idx++] = next + 'a';
        cnt[next]--;
      }
    }
  }
  ans[idx] = '\0';
  return ans;
}

int main() {
  char *s1 = "cczazcc", *s2 = "aababab";
  char *rls1 = repeatLimitedString(s1, 3);
  char *rls2 = repeatLimitedString(s2, 2);
  printf("%s\n", rls1); // expect: "zzcccac"
  printf("%s\n", rls2); // expect: "bbabaa"
  free(rls1), free(rls2);
}