Signal Cleanup Problem

Signal Cleanup Problem — ExecCode Medium DSA Practice

Solve the Signal Cleanup problem on ExecCode. Free online medium DSA practice in String. Write and run code in Java, C++, Python — no signup required to run.

Problem description

s is a binary string. It is clean when every 0 appears before every 1, so it has the form zero or more 0s followed by zero or more 1s. A clean string may be only 0s, only 1s, or some 0s followed by some 1s. It must never contain a 1 before a later 0. Return the minimum number of flips that make s clean. A flip changes 0 to 1 or 1 to 0. You are given: s — a binary string Return the minimum number of flips. Choose the position where the 0s end and the 1s begin. Flipping the 1s on the left of that cut and the 0s on the right produces a clean string.

Examples

Input {'s': '1100101'}; Output 3. Input {'s': '000111'}; Output 0. Input {'s': '111000'}; Output 3

Constraints

1 <= n <= 1e5 where n = s.length s consists of the characters 0 and 1 The empty prefix and the empty suffix are allowed Rescanning the string for every cut is O(n^2) and will Time Limit Exceed

Practice Signal Cleanup free on ExecCode. Browse DSA problems, topic map, and placement guides.