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.
Only original us can matter, because the only useful operation is changing u into s. So try maximizing how many us survive.
A u at the first or last position can never survive. Its two nearest s characters would both be on one side, so their distances cannot match.
If two us are adjacent in the final string, at least one of them has nearest s distances like and . That fails. Adjacent surviving us are dead on arrival.
An interior isolated u is always valid: it sits in sus, so the nearest s characters are both distance away.
Therefore, keep the maximum number of non-adjacent interior positions that are originally u. The answer is total number of us minus that maximum.
We can only set characters to s, so every operation that matters changes a u into an s. Existing s characters are already fine. So the real question is:
What is the largest number of original
us we can leave asu?
Then:
What can stay as u?
Take some final u at position .
If or , then all s characters are on only one side of it. The nearest two s characters have different distances, because they are at different positions on the same side. So edge us are impossible.
Now suppose two final us are adjacent. Look at a block of consecutive us. The u at the left end of that block has its nearest s on the left at some distance, while the nearest s on the right is farther away because at least one more u blocks the way. Those distances are not equal. Same idea from the right end. So any block of length at least is invalid. Consecutive surviving us are not allowed. Brutal, but clean.
On the other hand, if a u is isolated and not on an edge, then locally the string contains:
s u sThe two nearest s characters are exactly its neighbors, both distance away. That u is valid.
So we have the full characterization:
A final string is suspicious exactly when every remaining
uis interior and isolated, and there are at least twoscharacters.
The “at least two s” condition is automatically satisfied here for : an isolated interior u has two neighboring ss, and if there are no us left, the whole string is all s.
Optimization
We need to keep as many original us as possible such that:
This is just maximum independent set on a path, which is a tiny DP.
Let:
us so far if the previous position was not kept,us so far if the previous position was kept.For each position :
because we skip position .
If and is not an edge, we may keep it, but only if the previous position was skipped:
Otherwise is impossible.
At the end:
and the number of operations is:
The total complexity is per test case and memory. No drama, no weird casework hell.
#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 r;
cin >> r;
int n = (int)r.size();
int totalU = 0;
for (char c : r) totalU += (c == 'u');
const int NEG = -1e9;
int dp0 = 0, dp1 = NEG;
for (int i = 0; i < n; i++) {
bool canKeep = (r[i] == 'u' && i > 0 && i + 1 < n);
int ndp0 = max(dp0, dp1);
int ndp1 = canKeep ? dp0 + 1 : NEG;
dp0 = ndp0;
dp1 = ndp1;
}
int kept = max(dp0, dp1);
cout << totalU - kept << '\n';
}
}#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 r;
cin >> r;
int n = (int)r.size();
int totalU = 0;
for (char c : r) totalU += (c == 'u');
const int NEG = -1e9;
int dp0 = 0, dp1 = NEG;
for (int i = 0; i < n; i++) {
bool canKeep = (r[i] == 'u' && i > 0 && i + 1 < n);
int ndp0 = max(dp0, dp1);
int ndp1 = canKeep ? dp0 + 1 : NEG;
dp0 = ndp0;
dp1 = ndp1;
}
int kept = max(dp0, dp1);
cout << totalU - kept << '\n';
}
}