2225BUnreviewedunratedGPT-5.5 (high)

Alternating String

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force greedy

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

There are only two possible final strings: $abab\ldots$ and $baba\ldots$ . Try fixing one of them as the target and ask what the operation can change relative to it.

For a fixed alternating target $T$ , look at the positions where $s_i \ne T_i$ . Binary strings are nice: a mismatch means the character is exactly the complement of $T_i$ .

Reversing a substring of an alternating string gives either the same alternating pattern or its complement on that substring. Which one happens depends only on the parity of the substring endpoints.

So, relative to a fixed target $T$ , outside the chosen substring all positions must already match $T$ . Inside the chosen substring, either all positions match $T$ or all positions mismatch $T$ .

Dead giveaway: for each of the two targets $abab\ldots$ and $baba\ldots$ , compute all mismatch positions. The answer is YES iff for at least one target those mismatches form one contiguous block, or there are no mismatches at all.

Key observation

The final string must be one of only two strings:

ababab\ldots \quad \text{or} \quad bababa\ldots

Call one of them $T$ . We will check whether $s$ can be transformed into this fixed $T$ .

Use $0$ -based indices and encode characters as bits. For an alternating string,

T_i = x \oplus (i \bmod 2).

Suppose we choose substring $[l,r]$ and choose whether to invert it. Let the inversion flag be $c \in \{0,1\}$ , where $c=1$ means we invert.

After reversing, position $i$ inside $[l,r]$ receives the old character from position $l+r-i$ , possibly inverted:

\text{new}_i = s_{l+r-i} \oplus c.

We want $\text{new}_i = T_i$ .

Now comes the whole damn trick: in an alternating string, mirrored positions inside a segment differ by a constant depending only on $l+r$ :

T_{l+r-i} = T_i \oplus ((l+r) \bmod 2).

So inside the chosen substring, the original string $s$ must be either exactly equal to $T$ everywhere, or exactly the complement of $T$ everywhere. The inversion flag can handle either case.

Outside the chosen substring, nothing changes, so we must have:

s_i = T_i.

Therefore, relative to a fixed target $T$ , all mismatch positions must lie inside one substring, and inside that substring every position must mismatch. In other words:

The mismatch positions between $s$ and $T$ must form one contiguous block.

If there are no mismatches, $s$ is already alternating, so the answer is also YES.

Why this is sufficient

Assume the mismatch positions against some target $T$ form exactly one interval $[l,r]$ .

Then outside $[l,r]$ , $s_i=T_i$ . Inside $[l,r]$ , since the alphabet is binary and every position mismatches,

s_i = T_i \oplus 1.

Choose the substring $[l,r]$ . Pick inversion flag

c = 1 \oplus ((l+r) \bmod 2).

For every inside position $i$ :

\begin{aligned} \text{new}_i &= s_{l+r-i} \oplus c \\ &= T_{l+r-i} \oplus 1 \oplus c \\ &= T_i \oplus ((l+r) \bmod 2) \oplus 1 \oplus c \\ &= T_i. \end{aligned}

So the whole string becomes $T$ .

Algorithm

For each of the two alternating targets:

Scan the string.
Record the first mismatch position, last mismatch position, and number of mismatches.
If there are no mismatches, return YES.
Otherwise, the mismatches form one contiguous block iff

\text{count} = \text{last} - \text{first} + 1.

If either target passes, print YES; otherwise print NO.

Complexity

Each test case is scanned twice, so the complexity is

O(n)

per test case, and

O\left(\sum n\right)

over the whole input. Memory usage is

O(1).

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

bool ok(const string& s, char start) {
    int n = (int)s.size();
    int first = -1, last = -1, cnt = 0;

    for (int i = 0; i < n; i++) {
        char expected;
        if (i % 2 == 0) expected = start;
        else expected = (start == 'a' ? 'b' : 'a');

        if (s[i] != expected) {
            if (first == -1) first = i;
            last = i;
            cnt++;
        }
    }

    if (cnt == 0) return true;
    return cnt == last - first + 1;
}

int main() {
    setIO();

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;

        cout << (ok(s, 'a') || ok(s, 'b') ? "YES" : "NO") << '\n';
    }
}

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

bool ok(const string& s, char start) {
    int n = (int)s.size();
    int first = -1, last = -1, cnt = 0;

    for (int i = 0; i < n; i++) {
        char expected;
        if (i % 2 == 0) expected = start;
        else expected = (start == 'a' ? 'b' : 'a');

        if (s[i] != expected) {
            if (first == -1) first = i;
            last = i;
            cnt++;
        }
    }

    if (cnt == 0) return true;
    return cnt == last - first + 1;
}

int main() {
    setIO();

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;

        cout << (ok(s, 'a') || ok(s, 'b') ? "YES" : "NO") << '\n';
    }
}

View on Codeforces Back to the list