Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
There are only two possible final strings: and . Try fixing one of them as the target and ask what the operation can change relative to it.
For a fixed alternating target , look at the positions where . Binary strings are nice: a mismatch means the character is exactly the complement of .
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 , outside the chosen substring all positions must already match . Inside the chosen substring, either all positions match or all positions mismatch .
Dead giveaway: for each of the two targets and , 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.
The final string must be one of only two strings:
Call one of them . We will check whether can be transformed into this fixed .
Use -based indices and encode characters as bits. For an alternating string,
Suppose we choose substring and choose whether to invert it. Let the inversion flag be , where means we invert.
After reversing, position inside receives the old character from position , possibly inverted:
We want .
Now comes the whole damn trick: in an alternating string, mirrored positions inside a segment differ by a constant depending only on :
So inside the chosen substring, the original string must be either exactly equal to everywhere, or exactly the complement of everywhere. The inversion flag can handle either case.
Outside the chosen substring, nothing changes, so we must have:
Therefore, relative to a fixed target , all mismatch positions must lie inside one substring, and inside that substring every position must mismatch. In other words:
The mismatch positions between and must form one contiguous block.
If there are no mismatches, is already alternating, so the answer is also YES.
Assume the mismatch positions against some target form exactly one interval .
Then outside , . Inside , since the alphabet is binary and every position mismatches,
Choose the substring . Pick inversion flag
For every inside position :
So the whole string becomes .
For each of the two alternating targets:
YES.If either target passes, print YES; otherwise print NO.
Each test case is scanned twice, so the complexity is
per test case, and
over the whole input. Memory usage is
#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';
}
}