Overview

The maximum number of non-crossing pairs that can be formed with the modified \(s, t\) is the length of the LCS (Longest Common Subsequence) of the two strings.

At first glance, there seem to be many ways to modify the strings, but due to the constraints, the positions that can actually be changed are limited to essentially just the endpoints. For each string, we enumerate at most \(4\) possible states after modification and compute the LCS for each pair.

Analysis

First, let’s consider the pairing conditions.

A pair \((i,j)\) can only be formed when \(s_i=t_j\), and pairs must not cross each other.
This is equivalent to extracting the same string as a subsequence from both \(s\) and \(t\).

Therefore, if the modified strings are \(a, b\), the maximum number of pairs that can be formed is

\[ \mathrm{LCS}(a,b) \]

---

Next, let’s consider what modifications are possible.

The strings consist only of 0 and 1.
After flipping a position, that position must differ from all of its neighboring characters.

Interior positions cannot be changed

Suppose position \(i\) has neighbors on both sides.

For the flipped character to differ from both neighbors, the character before flipping must be the same as both neighbors.

In other words, before the change, there must be three consecutive identical characters like:

000

or

111

However, according to the problem statement, the initial strings \(s, t\) do not have any position where the same character appears \(3\) times consecutively.

Furthermore, even after performing allowed operations, the changed position becomes different from its neighbors, so no new run of \(3\) consecutive identical characters is ever created.

Therefore, interior positions can never be changed.

---

Only the endpoints can be changed

Endpoint positions have only one neighbor.

For example, when changing the left endpoint, it only needs to differ from its right neighbor after the change.
This is possible only when the left endpoint and its right neighbor are the same before the change.

Example:

00...

The left endpoint can be flipped to:

10...

On the other hand, for:

01...

Flipping the left endpoint would give:

11...

which makes it the same as its neighbor, so this is impossible.

Therefore, for strings of length \(3\) or more:

• The left endpoint can be changed if the first \(2\) characters are the same
• The right endpoint can be changed if the last \(2\) characters are the same

Since changes at both endpoints are independent of each other, there are at most \(4\) possible modified strings.

---

Short lengths are slightly special cases.

• Length \(1\):
  Since there are no neighbors, flipping is always possible.
• Length \(2\):
  If the \(2\) characters are the same, either the left or right one can be flipped.
  However, once one is flipped, the string becomes 01 or 10, and the other can no longer be flipped.

Algorithm

For each string, enumerate the reachable states.

For example, for string \(u\), create candidates as follows:

1. Add the original string with cost \(0\)
2. If length is \(1\):
   • Add the flipped string with cost \(1\)
3. If length is \(2\):
   • If \(u_0=u_1\), add the string with only the left flipped and the string with only the right flipped, each with cost \(1\)
4. If length is \(3\) or more:
   • If the first \(2\) characters are the same, the left endpoint can be flipped
   • If the last \(2\) characters are the same, the right endpoint can be flipped
   • Try all combinations of possible endpoint flips

This gives at most \(4\) states for each string.

Then, for all pairs of:

• Candidates from \(s\): \((a, c_a)\)
• Candidates from \(t\): \((b, c_b)\)

satisfying

\[ c_a+c_b \leq K \]

compute \(\mathrm{LCS}(a,b)\).

The maximum value among these is the answer.

The LCS is computed using standard dynamic programming.
\(dp[j]\) represents “the LCS length between the current prefix of \(a\) and the first \(j\) characters of \(b\)”, with space compressed to \(O(|t|)\).

Complexity

Let \(n\) be the length of \(s\) and \(m\) be the length of \(t\).

Since there are at most \(4\) candidates for each string, the LCS is computed at most \(16\) times.

• Time complexity: \(O(nm)\)
• Space complexity: \(O(n+m)\)

Since the constraint gives \(n \times m \leq 2 \times 10^6\), this runs sufficiently fast.

Implementation Notes

When generating candidate states, the same string might be produced in multiple ways, so we keep only the minimum cost for each distinct string.

Also, since the number of operations is “at most \(K\)”, a candidate state can be used as long as its minimum cost is at most \(K\).
There is no need to use extra operations.

Source Code

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

static inline void flip_char(char &c) {
    c = (c == '0' ? '1' : '0');
}

vector<pair<string,int>> generate_states(const string& u) {
    vector<pair<string,int>> res;

    auto add = [&](const string& v, int cost) {
        for (auto &p : res) {
            if (p.first == v) {
                p.second = min(p.second, cost);
                return;
            }
        }
        res.push_back({v, cost});
    };

    int n = (int)u.size();
    add(u, 0);

    if (n == 1) {
        string v = u;
        flip_char(v[0]);
        add(v, 1);
    } else if (n == 2) {
        if (u[0] == u[1]) {
            string v = u;
            flip_char(v[0]);
            add(v, 1);

            v = u;
            flip_char(v[1]);
            add(v, 1);
        }
    } else {
        bool canL = (u[0] == u[1]);
        bool canR = (u[n - 2] == u[n - 1]);

        for (int mask = 1; mask < 4; mask++) {
            if ((mask & 1) && !canL) continue;
            if ((mask & 2) && !canR) continue;

            string v = u;
            int cost = 0;

            if (mask & 1) {
                flip_char(v[0]);
                cost++;
            }
            if (mask & 2) {
                flip_char(v[n - 1]);
                cost++;
            }

            add(v, cost);
        }
    }

    return res;
}

int lcs_length(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<int> dp(m + 1, 0);

    for (int i = 0; i < n; i++) {
        int prev = 0;
        for (int j = 0; j < m; j++) {
            int tmp = dp[j + 1];
            if (a[i] == b[j]) {
                dp[j + 1] = max(dp[j + 1], prev + 1);
            } else {
                dp[j + 1] = max(dp[j + 1], dp[j]);
            }
            prev = tmp;
        }
    }

    return dp[m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    int K;
    cin >> s >> t >> K;

    auto ss = generate_states(s);
    auto tt = generate_states(t);

    int ans = 0;
    for (auto &[a, ca] : ss) {
        for (auto &[b, cb] : tt) {
            if (ca + cb <= K) {
                ans = max(ans, lcs_length(a, b));
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.