Show problems as
Classic problem #3499MediumStringEnumeration

Maximize Active Section with Trade I

Real-world version: Sign Segment Repair Pass
Tracked in this browser only
Read Maximize Active Section with Trade I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A shop sign is a strip of n segments described by the string strip, where '1' is a segment that is currently lit and '0' is one that is dark.

A technician gets one repair pass over the strip, and the pass has two steps taken in this order:

  1. Pick a stretch of consecutive segments that are all lit as the strip stands, and switch every segment in that stretch off.
  2. Pick a stretch of consecutive segments that are all dark in the strip step 1 left behind, and switch every segment in that stretch on.

Each stretch must be consecutive and must be uniform in the state its step calls for. Either stretch is allowed to be empty, and the two steps cannot be reordered or repeated.

Return the largest number of lit segments the sign can show once the pass is over.

Examples

Example 1

Input
strip = "1101000110"
Output
9

Switching off the lit segment at index 3 welds the dark segment at index 2 to the dark stretch at indices 4 through 6, and switching that whole stretch of five on leaves nine lit.

Example 2

Input
strip = "000101000"
Output
6

Switching off the lit segment at index 3 joins the dark stretch at indices 0 through 2 to the dark segment at index 4, and switching those four on leaves six lit.

Example 3

Input
strip = "10011101"
Output
8

Switching off nothing and then switching on the dark stretch at indices 1 and 2 leaves seven lit.

Constraints

  • 1 <= n == strip.length <= 10^5
  • strip[i] is either '0' or '1'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_lit_after_pass(strip: str) -> int:
Java
public int bestLitAfterPass(String strip)

More on the same topics