PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: arunsharma_
Tester: abhidot
Editorialist: iceknight1093
DIFFICULTY:
1381
PREREQUISITES:
None
PROBLEM:
Given a binary string S, consider another binary string X such that X_{i+1} = S_i \oplus X_i for each 1 \leq i \lt N.
Find the maximum number of ones such a string can have.
EXPLANATION:
Note that one X_1 is fixed, the rest of the string is uniquely determined, since:
- X_2 = X_1 \oplus S_1
-
X_3 = X_2\oplus S_2
\vdots
But X is a binary string, so there are only two choices for X_1 — it can be either 0 or 1.
Simply try both options, construct the respective strings, and see which one has the maximum number of ones.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
ct1, ct2 = 0, 0
prv = '0'
for i in range(1, n):
if s[i-1] == prv: prv = '0'
else: prv = '1'
ct1 += prv == '1'
ct2, prv = 1, '1'
for i in range(1, n):
if s[i-1] == prv: prv = '0'
else: prv = '1'
ct2 += prv == '1'
print(max(ct1, ct2))