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.
Think about what a character means after some operations. A resulting Y is not just one original Y; it means that whole merged block contains at least one Y.
The only forbidden move is merging two blocks that both contain a Y. So once two separate Y-containing blocks exist next to each other, they can never be merged.
If the original string has zero Ys, every operation is N OR N = N, so it is always possible.
If the original string has exactly one Y, you can safely merge all Ns into it one by one. Every merge involving that block is Y with N, never Y with Y.
If the original string has two or more Ys, the final single character would have to contain all of them. The last operation would need to merge two parts; both cannot contain Y, so all Ys must already be in one part. Chase that backward and eventually two Y-containing things would need to merge. Impossible. So the answer is YES iff the number of Ys is at most .
Core idea
Every current character represents some contiguous block of the original string.
N means that block contains only original Ns.Y means that block contains at least one original Y.The operation is just merging two adjacent blocks and labeling the merged block with OR.
The forbidden move is exactly this: you may not merge two blocks that both contain at least one Y. That's the whole problem. No hidden DP boss fight here.
Case 1: no Ys
If the string is all N, then every operation is:
No move is forbidden, so we can keep merging until one character remains.
Answer: YES.
Case 2: exactly one Y
There is only one Y-containing block in the entire string. Merge neighboring N blocks into it, or merge Ns among themselves first. Any merge involving the Y block is either:
or
Never Y OR Y, because there is only one original Y in existence. So reduction is always possible.
Answer: YES.
Case 3: at least two Ys
Suppose reduction were possible. At the end, we have one final block containing the whole string, so it contains at least two original Ys.
Look at the operation that created this final block. It merged two adjacent blocks. Since the move was legal, not both blocks could contain a Y. Therefore, all original Ys must have already been inside just one of those two blocks before the final merge.
Apply the same logic to that block. It also contains at least two original Ys, so the operation that created it must have merged one block containing all those Ys with another block containing none.
Keep going backward. This says the multiple Ys were somehow always together in one block without ever merging two Y-containing blocks. But initially, each Y is its own separate Y-containing block. To get two of them into the same block, at some point you must merge two blocks that each contain a Y. That move is forbidden. Brutal, but fair.
So with two or more Ys, it is impossible.
Answer: NO.
Final condition
The string is reducible iff:
So for each test case, just count the Ys. If the count is at most , print YES; otherwise print NO.
Complexity
For each test case, we scan the string once.
Time complexity:
Memory complexity:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int y = 0;
for (char c : s) {
if (c == 'Y') y++;
}
cout << (y <= 1 ? "YES" : "NO") << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int y = 0;
for (char c : s) {
if (c == 'Y') y++;
}
cout << (y <= 1 ? "YES" : "NO") << '\n';
}
return 0;
}