C++ Run-Length Decoding Algorithm

Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as a single count and character. For example, the string “AAAABBBCCDAA” would be encoded as “4A3B2C1D2A”.

Given a string s that’s a run-length encoded string, return its decoded version.
Note: The original string is guaranteed not to have numbers in it.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “4A3B2C1D2A”
Output
“AAAABBBCCDAA”

Run-Length Decoding Algorithm in C++

Given a encoded run-length string, we can go through the string and parse the counter and its repeated string part. Then we can construct the decoded string on the fly. This is based on the assumption that the original un-encoded string does not contain numbers/digits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

string solve(string s) {
    int i = 0;
    string ans = "";
    while (i < s.size()) {
        int j = i;
        while (isdigit(s[j]) && (j < s.size())) {
            j ++;
        }
        int a = stoi(s.substr(i, j - i + 1));
        int k = j;
        while (isalpha(s[k]) && k < s.size()) {
            k ++;
        }
        auto t = s.substr(j, k - j);
        for (int k = 0; k < a; ++ k) {
            ans += t;
        }
        i = k;
    }    
    return ans;
}

string solve(string s) {
    int i = 0;
    string ans = "";
    while (i < s.size()) {
        int j = i;
        while (isdigit(s[j]) && (j < s.size())) {
            j ++;
        }
        int a = stoi(s.substr(i, j - i + 1));
        int k = j;
        while (isalpha(s[k]) && k < s.size()) {
            k ++;
        }
        auto t = s.substr(j, k - j);
        for (int k = 0; k < a; ++ k) {
            ans += t;
        }
        i = k;
    }    
    return ans;
}

The time complexity is O(N) where N is the length of the string since we need to iterate one pass of the string. The space complexity is O(M) where M is the original un-encoded string.

–EOF (The Ultimate Computing & Technology Blog) —