Coding Errors (Editorial)

Idea

We are given two binary strings $s$ and $g$ of length $n$. Among all cyclic shifts of the string $g$, we need to find the one for which the number of errors is minimal. An error is the number of maximal subsegments on which the corresponding characters of the strings differ (that is, the number of "blocks" of consecutive positions where s_i \neq g'_i).

Key observation

There are exactly $n$ cyclic shifts. For each shift, we can count the number of mismatch blocks in one pass: we go from left to right, and every time we encounter a position where s_i \neq g'_i, while the previous position either matched or this is the beginning of the string, a new block starts.

Since n \le 4 \cdot 10^3 and the sum of all $n$ does not exceed 4 \cdot 10^3, we can afford to try all $n$ shifts and compute the answer for each in $O(n)$.

How to implement a cyclic shift?

Instead of building a new string every time, we can simply shift $g$ in place. At each step, we take the last character of the string $g$ and put it at the beginning — this is one cyclic shift to the right:

Counting mismatch blocks

For a fixed shift, we traverse the string and maintain a flag $streak$: whether we are currently "inside" a mismatch block. If s_i \neq g_i and \mathit{streak} = \mathit{false} — a new block starts, so we increase the counter. If the characters match — we reset $streak$.

The answer is the minimum over all shifts.

Complexity

There are $n$ shifts, and for each we count blocks in $O(n)$.

Thus, we get O(n^2) for one test case, and O\!\left(\left(\sum n\right)^2\right) overall, which under the problem constraints does not exceed O\!\left((4 \cdot 10^3)^2\right) = O(1{,}6 \cdot 10^7).

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'

const ll INF = 1e18;

void solve() {
    ll n;
    string s, s1;
    cin >> n;
    cin >> s >> s1;

    ll res = INF;

    for (int step = 1; step <= n; step++) {
        bool streek = 0;
        ll curr = 0;

        for (int i = 0; i < n; i++) {
            if (s[i] != s1[i]) {
                if (!streek) {
                    streek = 1;
                    curr++;
                }
            } else {
                streek = 0;
            }
        }

        res = min(res, curr);

        // cyclic shift: last character becomes first
        s1 = s1[s1.size() - 1] + s1;
        s1.pop_back();
    }

    cout << res << endl;
}

signed main() {
    speed;
    int test;
    cin >> test;
    while (test--) solve();
    return 0;
}