GOODBINSTR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Varun Vaddiraju
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh

DIFFICULTY:

1573

PREREQUISITES:

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.

Answer

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))
2

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;
}