# GOODBINSTR - Editorial

Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh

1573

None

# PROBLEM:

Given a binary string S, find the number of indices such that flipping the value at this index makes S have an equal number of \texttt{01} and \texttt{10} substrings.

# EXPLANATION:

Suppose there are x occurrences of \texttt{01} and y of \texttt{10} as substrings in S.
We’d like to count the number of flips that makes x = y.

First, let’s analyze how the given operation affects x and y.

First, consider flipping 1 \lt i \lt N.

• If S_{i-1} \neq S_{i+1}, then there is no change in either x or y.
• If S_{i-1} = S_{i+1}, then
• If S_i = S_{i-1}, then x and y both increase by 1
• If S_i \neq S_{i-1}, then x and y both decrease by 1

You might notice that, in any case, x - y doesn’t change.
So, flipping a ‘middle’ index can give us x = y if and only if x = y initially: and if this is the case, then flipping any of the middle indices will give us a good binary string.

That leaves only the endpoints of the strings. Flipping those affects x or y by 1 — the exact change can be caseworked since it only depends on (S_1, S_2) and (S_{N-1}, S_N).

This already gives us a fast enough solution:

• First, compute x and y as described above. This is easy to do in \mathcal{O}(N).
• If x = y, then the answer is N-2.
• Then, there are only two more cases: flipping the first and the last character. Simply perform both flips and check whether they make the resulting string good in \mathcal{O}(N) each.

However, there’s an even simpler implementation.
The key observation is to notice that, if S_1 = S_N, then we will have x = y; and otherwise x and y will differ by exactly 1.

Why?

This is not hard to see: the idea is that essentially, ‘blocks’ of the same character can be treated as a single character.

So, suppose S_1 = 0. Then, note that you will alternately encounter \texttt{01} and \texttt{10} as substrings.
Thus, if S_1 = S_N, both occur an equal number of times; otherwise \texttt{01} occurs one more time than \texttt{10}.

This observation leads us to a very simple solution:

• If S_1 = S_N, the answer is N-2: flip any of the middle characters.
• Otherwise, the answer is always 2: flipping either of the end characters will make S_1 = S_N and hence x = y.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>

using namespace std;

int main()
{
int t;
cin >> t;

while (t--)
{
string s;
cin >> s;

if (s[0] == s[s.size()-1])
{
cout << s.size()-2 << "\n";
}
else
{
cout << "2\n";
}
}
}

Editorialist's code (Python)
def calc(s):
n = len(s)
zo, oz = 0, 0
for i in range(n-1):
if s[i] == s[i+1]: continue
if s[i] == '0': zo += 1
else: oz += 1
return zo - oz

for _ in range(int(input())):
s = input()
if len(s) == 1: print(1)
else:
if calc(s) == 0: print(len(s)-2)
else: print(int(calc(chr(97 - ord(s[0])) + s[1:]) == 0) + int(calc(s[:len(s)-1] + chr(97 - ord(s[-1]))) == 0))


Trying to approach this problem with two pointer approach , Take a long time to code

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

#define int     long long int

void solve(){
string s;
cin>>s;

int zo = 0, oz = 0;
for(int i=0;i<s.size()-1;i++){
string sub = s.substr(i,2);
if(sub == "10") oz++;
if(sub == "01") zo++;
}

if(s.size() == 2){
if(s == "10" or s == "01"){
cout<<2<<endl;
}else cout<<0<<endl;
return;
}

int defzo = zo,defoz = oz;

if(s[0] == '0' and s[1] == '1'){ // 01 11
zo--;
}else if(s[0] == '1' and s[1] == '0'){ // 10 00
oz--;
}else if(s[0] == '1' and s[1] == '1'){ // 11 01
zo++;
}else if(s[0] == '0' and s[1] == '0'){ // 00 10
oz++;
}

int cnt = 0;
if(oz == zo){
cnt++;
}
int r=1,n = s.size();
while(r < n -1){
zo = defzo;
oz = defoz;

if(s[r-1] == '0' and s[r] == '0' and s[r+1] == '0') zo++,oz++;
if(s[r-1] == '0' and s[r] == '1' and s[r+1] == '0') zo--,oz--;
if(s[r-1] == '1' and s[r] == '0' and s[r+1] == '1') zo--,oz--;
if(s[r-1] == '1' and s[r] == '1' and s[r+1] == '1') zo++,oz++;

if(oz == zo){
cnt++;
}
r++;
}

defzo = zo,defoz = oz;
if(s[n-1] == '0' and s[n-2] == '1'){ // 10      11
oz--;
}else if(s[n-1] == '1' and s[n-2] == '0'){ // 01  00
zo--;
}else if(s[n-1] == '1' and s[n-2] == '1'){ // 11  10
oz++;
}else if(s[n-1] == '0' and s[n-2] == '0'){ // 00  01
zo++;
}

if(oz == zo){
cnt++;
}

cout<<cnt<<" "<<endl;
}

signed main() {
int t=1;
cin>>t;
while(t--) solve();
return 0;
}