Show problems as
Classic problem #3501HardArrayStringBinary SearchSegment Tree

Maximize Active Section with Trade II

Real-world version: Most Lit Segments in a Window
Tracked in this browser only
Read Maximize Active Section with Trade II 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 segments described by strip, where '1' is a segment that is lit and '0' is one that is dark.

Each entry queries[j] = [lo, hi] asks about the stretch of segments from lo to hi inclusive. The queries are independent: the strip itself is never changed, and every query starts from the strip as given.

Within the stretch a technician gets one repair pass, whose two steps are taken in this order.

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

The two runs need not be the same length, either may be empty, and neither may reach outside the stretch. The steps cannot be reordered or repeated.

Return an array best where best[j] is the largest number of lit segments the j-th stretch can show once its pass is over.

Examples

Example 1

Input
strip = "1100011", queries = [[0, 6], [2, 4], [0, 3]]
Output
[7, 3, 4]

For the whole strip, switching nothing off and switching the three dark segments on shows seven lit segments. For the stretch from 2 to 4 every segment is dark, and switching all three on shows three. For the stretch from 0 to 3 the two dark segments can be switched on, showing four.

Example 2

Input
strip = "0010100", queries = [[0, 6], [2, 4], [1, 5]]
Output
[5, 3, 4]

Across the whole strip, switching off the lit segment at position 3 leaves seven dark segments in a row, and switching them all on shows seven lit segments. The stretch from 2 to 4 reads lit, dark, lit and can show three. The stretch from 1 to 5 can show five.

Example 3

Input
strip = "111", queries = [[0, 2]]
Output
[3]

Every segment is already lit, so the best pass switches nothing off and nothing on.

Constraints

  • 1 <= strip.length <= 10^5
  • strip[i] is either '0' or '1'
  • 1 <= queries.length <= 10^5
  • queries[j].length == 2
  • 0 <= queries[j][0] <= 99999
  • 0 <= queries[j][1] <= 99999
  • Every query satisfies lo <= hi < strip.length

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_in_window(strip: str, queries: list[list[int]]) -> list[int]:
Java
public List<Integer> bestLitInWindow(String strip, int[][] queries)

More on the same topics