leetcode

0 class Solution {

1 public:

2 string repeatLimitedString(const string &s, int limit) const {

3 int count[27] = {0};

4 for (const char c : s)

5 count[c & 0x1F]++;

6

7 typedef tuple<char, int> record;

8 priority_queue<record> pq;

9

10 for (int i = 1; i <= 26; i++) {

11 if (!count[i]) continue;

12 pq.emplace('`' + i, count[i]);

13 }

14

15 string res;

16 char last = '~';

17 while (!empty(pq)) {

18 const auto [c, cnt] = pq.top();

19 pq.pop();

20 if (c == last) {

21 if (pq.empty()) break;

22

23 const auto [oc, ocnt] = pq.top();

24 pq.pop();

25 pq.emplace(c, cnt);

26

27 res += oc;

28 if (ocnt > 1) pq.emplace(oc, ocnt - 1);

29

30 last = oc;

31 } else {

32 res += string(min(cnt, limit), c);

33 if (cnt > limit) pq.emplace(c, cnt - limit);

34 last = c;

35 }

36 }

37

38 return res;

39 }

40 };

41

42 // O(1) space, no priority_queue

43 class Solution {

44 public:

45 string repeatLimitedString(const string &s, int limit) const {

46 int count[27] = {0};

47 for (const char c : s)

48 count[c & 0x1F]++;

49

50 string res;

51 int i;

52

53 for (i = 26; i >= 0; i--)

54 if (count[i]) break;

55 if (count[i] == size(s)) return string(min(limit, count[i]), '`' + i);

56

57 int j = i - 1;

58 while (i > 0) {

59 res += string(min(limit, count[i]), '`' + i);

60 if (limit < count[i]) {

61 while (j >= 0 && !count[j])

62 j--;

63 if (j < 0) break;

64

65 res += '`' + j;

66

67 count[i] -= limit;

68 count[j]--;

69 } else {

70 i = j;

71 j = i - 1;

72 }

73 }

74

75 return res;

76 }

77 };