PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You have a binary string S.
In one move, you can choose three indices i \lt j \lt k such that S_i \neq S_j and S_j \neq S_k, and delete S_j.
Find the minimum possible final length of S.
EXPLANATION:
Analyzing the move allowed to us, we can see that it essentially boils down to:
choose a subsequence of the string that equals either \textbf{010} or \textbf{101}, and delete the middle character.
In particular, since we’re always deleting the middle character, note that we’ll never be able to delete either the first or the last character of S, i.e. they’ll always remain in the final string.
Let’s use this fact to analyze a couple of different combinations of the first/last character.
First, suppose S_1 = S_N = \textbf{0}, i.e. the string starts and ends with \textbf{0}.
Now, we can see that it’s always possible to delete every \textbf{1} in the string, by using the first and last characters.
So, the goal now is to delete as many zeros from the string as possible first - then we can delete all the ones.
This is now quite simple.
Let L be the index of the leftmost occurrence of a \textbf{1} in the string, and R be the index of the rightmost occurrence.
Then, we can delete every \textbf{0} between L and R, and we can’t delete any \textbf{0} outside of them.
Since we’re able to delete every \textbf{1} in the string, this means we’re essentially able to delete every character in the range [L, R], and nothing outside of it.
So, the answer in this case is just L-1 + (N-R), i.e. the sum of the lengths of the segments [1, L-1] and [R+1, N].
The case of S_1 = S_N = \textbf{1} is similar, just with the roles of zero and one flipped.
Next, let’s consider the case where S_1 = \textbf{0} and S_N = \textbf{1}.
Here, let L denote the leftmost occurrence of \textbf{1}, and R denote the rightmost occurrence of \textbf{0}.
Observe that:
- Using indices 1 and R, we can delete any occurrence of \textbf{1} in the range [1, R], but nothing after R.
- Using indices L and N, we can delete any occurrence of \textbf{0} in the range [L, N], but nothing before L.
There are now two cases.
- Case 1: L \lt R.
This means all the zeros appear before all the ones, i.e. the string is \textbf{000}\ldots\textbf{111}
In this case, no deletions can be made at all, so the answer is N. - Case 2: L \gt R.
In this case, we’ll surely have everything in the ranges [1, L-1] and [R+1, N] remaining.
However, this time it’s not possible to delete everything in [L, R]: no matter what we do, at least one element in that range will remain.
So, the answer here is (L-1) + (N-R) + 1.
To see why at least one element in [L, R] will remain: if we are to delete the last element in [L, R], it must be done using one element before L and one element after R; however everything before L is a \textbf{0} and everything after R is a \textbf{1}, so performing a valid move is impossible.
The case of S_1 = \textbf{1} and S_N = \textbf{0} is symmetric.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
if (s[0] == '1') {
for (auto &c : s)
c ^= '0'^'1';
}
if (s.back() == '0') {
int l = 0, r = n-1;
while (l <= r) {
if (s[l] == '0') ++l;
else if (s[r] == '0') --r;
else break;
}
if (l <= r) cout << l + n-1-r << '\n';
else cout << n << '\n';
}
else {
int l = 0, r = n-1;
while (s[l] == '0') ++l;
while (s[r] == '1') --r;
if (l <= r) cout << l + n-r << '\n';
else cout << n << '\n';
}
}
}