219C - Color Stripe - CodeForces Solution

#pragma GCC optimize ("O3")

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

#define ll long long
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
using namespace std;

const int OO = 0x3f3f3f3f, N = 5e5 + 5, mod = 1e9 + 7;

int n, k;
string s;
int dp[N][30];

int go(int idx, int lst) {
    if (idx == n) {
        return 0;
    }

    if (dp[idx][lst] != -1)
        return dp[idx][lst];

    int ans = 1e9;
    for (int i = 0; i < k; i++) {
        if (lst != i)
            ans = min(ans, go(idx + 1, i) + (s[idx] != (char) (i + 'A')));
    }
    return  dp[idx][lst] = ans;
}

void print(int idx, int lst) {
    if (idx == n) {
        return;
    }
    for (int i = 0; i < k; i++) {

        if (i != lst && go(idx + 1, i) + ((s[idx] - 'A') != i) == dp[idx][lst]) {
            cout << (char) (i + 'A');
            print(idx + 1, i);
            return;
        }

    }
}

int main() {
    fast;
    memset(dp, -1, sizeof dp);
    cin >> n >> k;
    cin >> s;
    cout << go(0, 29) << endl;
    print(0, 29);
}