Lossy Run-Length Encoding - Microsoft Top Interview Questions

                        Solution in C++ :

struct state {
    int lhs, rhs;
    int total;
    state() {
    }
    state(int a, int b) {
        lhs = a;
        rhs = b;
        total = 0;
    }
};
int lenof(int x) {
    if (x == 1) return 0;
    return to_string(x).size();
}
void update(state& prev, state& curr) {
    curr.total = prev.total + lenof(curr.rhs - curr.lhs + 1) + 1;
}
class Solution {
    public:
    int solve(string s, int k) {
        int n = s.size();
        if (n == k) return 0;
        vector<state> lhs;
        lhs.emplace_back(-1, -1);
        for (int i = 0; i < n - k; i++) {
            if (i == 0 || s[i] != s[i - 1]) {
                lhs.emplace_back(i, i);
            } else {
                lhs.back().rhs++;
            }
            update(lhs[lhs.size() - 2], lhs.back());
        }
        // initial estimate - delete the entire suffix
        int ret = lhs.back().total;
        vector<state> rhs;
        rhs.emplace_back(n, n);
        for (int i = n - k - 1; i >= 0; i--) {
            // add the rightmost unadded character to the right side
            int add = i + k;
            if (add == n - 1 || s[add] != s[add + 1]) {
                rhs.emplace_back(add, add);
            } else {
                rhs.back().lhs--;
            }
            update(rhs[rhs.size() - 2], rhs.back());
            // remove the rightmost added character from the left
            if (lhs.back().lhs == lhs.back().rhs) {
                lhs.pop_back();
            } else {
                lhs.back().rhs--;
            }
            if (lhs.size() > 1) {
                update(lhs[lhs.size() - 2], lhs.back());
            }
            // new naive estimate, just stick the two together
            ret = min(ret, lhs.back().total + rhs.back().total);
            // is it possible that the two ends can be stuck together?
            if (lhs.size() > 1 && rhs.size() > 1 && s[lhs.back().rhs] == s[rhs.back().lhs]) {
                // add together all the components that are not involved in the merge
                int cand = lhs[lhs.size() - 2].total + rhs[rhs.size() - 2].total;
                // recompute the compressed length
                int tot = rhs.back().rhs - rhs.back().lhs + 1;
                tot += lhs.back().rhs - lhs.back().lhs + 1;
                cand += lenof(tot) + 1;
                ret = min(ret, cand);
            }
        }
        return ret;
    }
};


int solve(string s, int k) {
    return (new Solution())->solve(s, k);
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, S, K):
        N = len(S)
        if N == K:
            return 0

        left = [1] * N
        for i in range(N - 1):
            if S[i] == S[i + 1]:
                left[i + 1] = left[i] + 1

        right = [1] * N
        for i in reversed(range(N - 1)):
            if S[i] == S[i + 1]:
                right[i] = right[i + 1] + 1

        def rle(x):
            return x if x <= 1 else len(str(x)) + 1

        R = [len(list(g)) for _, g in groupby(S)]

        prefix = [0] * N
        prev = 0
        i = 0
        for x in R:
            for j in range(1, 1 + x):
                prefix[i] = prev + rle(j)
                i += 1
            prev += rle(x)

        suffix = [0] * N
        prev = 0
        i = N - 1
        for x in reversed(R):
            for j in range(1, 1 + x):
                suffix[i] = prev + rle(j)
                i -= 1
            prev += rle(x)

        ans = min(prefix[~K], suffix[K])
        for i in range(len(S) - K - 1):
            cand = prefix[i] + suffix[i + K + 1]
            lv = left[i]
            rv = right[i + K + 1]
            if S[i] == S[i + K + 1]:
                cand -= rle(lv) + rle(rv)
                cand += rle(lv + rv)
            ans = min(ans, cand)
        return ans