Show problems as
Classic problem #1221EasyStringGreedyCounting

Split a String in Balanced Strings

Real-world version: Most Even Conveyor Segments
Tracked in this browser only
Read Split a String in Balanced Strings on LeetCode(opens in a new tab)

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

A conveyor gate writes one character per event into log: 'I' when a crate comes in and 'O' when a crate goes out.

Call a run of consecutive events even when it records exactly as many 'I' events as 'O' events. Cut the whole log into consecutive non-empty runs so that every run is even, using every event exactly once and keeping the events in order.

Return the largest number of runs such a cut can produce. The log as a whole is even, so at least one such cut always exists.

Examples

Example 1

Input
log = "IOIOIO"
Output
3

Cutting after every second event gives the runs "IO", "IO" and "IO", each recording one arrival and one departure, so three runs is achievable.

Example 2

Input
log = "IIOOIO"
Output
2

The runs "IIOO" and "IO" use every event in order and each is even, giving two runs.

Example 3

Input
log = "OIOIIO"
Output
3

The runs "OI", "OI" and "IO" are all even, so three runs is achievable. A run may start with a departure.

Constraints

  • 2 <= log.length <= 1000
  • log[i] is either 'I' or 'O'.
  • log records the same number of 'I' events as 'O' events.

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 most_even_segments(log: str) -> int:
Java
public int mostEvenSegments(String log)

More on the same topics