PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given a binary string S denoting Alice’s attendance on N different days.
Alice can choose any contiguous segment of days such that she was absent on all of them, and mark herself present on these days (by submitting a medical certificate).
What’s the maximum possible number of days that she can be marked present on?
EXPLANATION:
Alice can choose only one segment to turn from absent to present; so clearly it’s optimal to choose the longest one.
So, the problem reduces to: given a binary string S, find its longest substring that consists of only zeros.
Equivalently, we want to find the largest distance between two consecutive ones in S.
This can be computed in linear time as follows:
- Let \text{mx} be a variable denoting the longest substring of zeros in the string so far.
Initially, this is 0. - Let \text{prv} denote the index of the last 1 we saw in S.
Initially, this is also 0. - Then, for each i from 1 to N:
- If S_i = 0, do nothing.
- If S_i = 1, set \text{mx} := \max(\text{mx}, i-\text{prv} - 1); considering the block of zeros between this 1 and the previous.
Then, update \text{prv} := i.
- At the end of this loop, don’t forget to set \text{mx} := \max(\text{mx}, N-\text{prv}), to account for the final block of zeros.
\text{mx} is now the maximum number of zeros that can be converted to ones.
The final answer is thus \text{mx}, plus the number of ones already in S.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
ct = s.count('1')
cur, mx = 0, 0
for c in s:
if c == '0': cur += 1
else: cur = 0
mx = max(mx, cur)
print(ct + mx)