1063. Planting Without Touching

A row of flowerbeds is given as a string of 0 for empty and 1 for already planted. No two planted beds are adjacent to begin with. You may plant in empty beds, and after planting, no two planted beds may be adjacent either.

Print the largest number of new flowers you can plant.

10001 -> 1 only the middle bed 00000 -> 3 beds 0, 2 and 4 10101 -> 0 000 -> 2

## What most people try first

Try every subset of the empty beds: 2^n with n at 100000. With a table over (position, was the previous bed planted) it becomes O(n), and that is the same "no two adjacent" recurrence as problem #451. It is correct and it is twice as much code as the greedy.

The instinct to AVOID is scanning for runs of zeros and applying a formula such as length / 2. That formula is right only for a run bounded by planted beds on BOTH sides, and the runs at the two ends of the row are bounded on one side only. Getting all three cases right by formula is more error-prone than the sweep.

## Plant at the first legal bed, every time

for i from 0 to n-1: if bed[i] == '0' and (i == 0 or bed[i-1] == '0') and (i == n-1 or bed[i+1] == '0'): bed[i] = '1' count += 1

The bed is MODIFIED as you go, which is what stops two new flowers landing next to each other: when i + 1 is examined, bed[i] already reads 1.

## Why planting as early as possible is optimal

Take any legal planting and look at its leftmost new flower, at position q. Let p be the first position the greedy plants in. Then p <= q, because q was legal and the greedy plants at the first legal position.

Move that flower from q to p. The result is still legal: p was legal in the ORIGINAL row, and the only flowers that could conflict with it are new ones to its right, which all sit at positions greater than q >= p, hence at least p + 2 away only if... and here is the one thing to check, that the second-leftmost new flower is at least p + 2. It is at least q + 2, and q >= p, so it is at least p + 2. The count is unchanged.

Repeating on the rest of the row turns any planting into the greedy one without losing a flower, so the greedy is at least as good as all of them.

## The two ends

i == 0 has no left neighbour and i == n - 1 has no right neighbour, and both count as empty. A solution that reads bed[-1] or bed[n] either crashes or silently reads whatever is there. The single-bed row 0 answers 1 and exercises both ends at once.

## Overflow

The answer is at most (n + 1) / 2, so at most 50001. The 32 bit limit of 2147483647 is not in play.

## Cost

Time O(n). Space O(n) if the row is modified in place, O(1) if you carry the previous bed's state in a variable instead.

Constraints - `1 ≤ length ≤ 100000` - the line contains only `0` and `1` - no two `1`s are adjacent in the input