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