Rcd, C++ (gcc) - rextester

Language: Layout:

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;

string remdupright(string s, bool allowEmpty) {
    if (s.size() >= 3) {
        auto pos = s.find_last_not_of(s.back());
        if (pos == string::npos && allowEmpty) s = "";
        else if (pos != string::npos && s.size() - pos > 3) s = s.substr(0, pos + 1);
    }
    return s;
}

string remdupleft(string s, bool allowEmpty) {
    if (s.size() >= 3) {
        auto pos = s.find_first_not_of(s.front());
        if (pos == string::npos && allowEmpty) s = "";
        else if (pos != string::npos && pos >= 3) s = s.substr(pos);
    }
    return s;
}

string remdup(string s, bool allowEmpty) {
    return remdupleft(remdupright(s, allowEmpty), allowEmpty);
}

string run(const string in) {
    vector<vector<string>> table(in.size());
    for (int i = 0; i < (int)table.size(); ++i) {
        table[i].resize(in.size() - i);
    }
    for (int i = 0; i < (int)table[0].size(); ++i) {
        table[0][i] = in.substr(i,1);
    }

for (int len = 2; len <= (int)table.size(); ++len) {
        for (int pos = 0; pos < (int)in.size() - len + 1; ++pos) {
            string base(table[len - 2][pos]);
            const char suffix = in[pos + len - 1];
            if (base.size() && suffix != base.back()) {
                base = remdupright(base, false);
            }
            const string opt1 = base + suffix;

base = table[len - 2][pos+1];
            const char prefix = in[pos];
            if (base.size() && prefix != base.front()) {
                base = remdupleft(base, false);
            }
            const string opt2 = prefix + base;

const string nodupopt1 = remdup(opt1, true);
            const string nodupopt2 = remdup(opt2, true);

table[len - 1][pos] = nodupopt1.size() > nodupopt2.size() ? opt2 : opt1;
            assert(nodupopt1.size() != nodupopt2.size() || nodupopt1 == nodupopt2);
        }
    }
    string& res = table[in.size() - 1][0];
    return remdup(res, true);
}

void testRcd(string s, string expected) {
    cout << s << " : " << run(s) << ", expected: " << expected << endl;
}

int main()
{
    testRcd("BAABCCCBBA", "B");
    testRcd("AABBAAAC", "AABBC");
    testRcd("AAAA", "");
    testRcd("AAAABBBAC", "C");
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.64 sec, absolute running time: 0.18 sec, cpu time: 0.09 sec, memory peak: 3 Mb, absolute service time: 0,82 sec