3.8.2 Run-Length Encoding

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

/*

Encodes consecutive equal characters as (`character`, `count`) runs. Run-length encoding is a simple
lossless compression technique that works well when strings contain long repeated blocks and poorly
when repetitions are rare.

The representation below stores runs in a vector of pairs rather than formatting them as a string.
This avoids ambiguity when the original text contains digits or separator characters.

- `run_length_encode(s)` returns the sequence of runs in string `s`.
- `run_length_decode(runs)` reconstructs the original string from a sequence of runs.

Time Complexity:
- O(n) per call, where $n$ is the input or output length.

Space Complexity:
- O(r) for encoded output, where $r$ is the number of runs.
- O(n) for decoded output.

*/

#include <string>
#include <utility>
#include <vector>
using std::string;

std::vector<std::pair<char, int>> run_length_encode(const string &s) {
  std::vector<std::pair<char, int>> res;
  for (char c : s) {
    if (res.empty() || res.back().first != c) {
      res.emplace_back(c, 1);
    } else {
      res.back().second++;
    }
  }
  return res;
}

string run_length_decode(const std::vector<std::pair<char, int>> &runs) {
  string res;
  for (auto [c, count] : runs) {
    res.append(count, c);
  }
  return res;
}

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  string s = "aaabccccdd";
  vector<pair<char, int>> runs = run_length_encode(s);
  assert((runs == vector<pair<char, int>>{{'a', 3}, {'b', 1}, {'c', 4}, {'d', 2}}));
  assert(run_length_decode(runs) == s);
  assert(run_length_encode("").empty());
  assert(run_length_decode({}) == "");
  assert((run_length_encode("z") == vector<pair<char, int>>{{'z', 1}}));
  return 0;
}