Maximum Consecutive Ones with Minimum Swaps - Expedia Online Assessment DTU

Problem Preview

"Pattern: 2 DSA + 1 SQL You are given a binary string `s` of length `n`, containing only `'0'` and `'1'`. You may perform a **swap** between any two positions in the string. Your goal is to make all the `1`s form one contiguous segment. Find the **minimum number of swaps** required to obtain the maximum possible length of consecutive `1`s. ### Input * The first line contains an integer `n` — the length of the binary string. * The second line contains the binary string `s`. ### Output Print a single integer — the minimum number of swaps required to make all `1`s consecutive. ### Constraints * `1 ≤ n ≤ 2 × 10^5` * `s` consists only of `'0'` and `'1'`. * The string contains at least one `1`. ### Examples **Example 1** ```text Input: 8 10010011 Output: 1 ``` **Explanation:** There are four `1`s. We can make them consecutive as `01111000` using one swap. **Example 2** ```text Input: 7 1010101 Output: 2 ``` **Explanation:** There are four `1`s. Choosing a window of length `4`, such as `1010`, requires two swaps to make it `1111`. **Example 3** ```text Input: 5 11101 Output: 0 ``` **Explanation:** The first three `1`s are already consecutive, so no swaps are required."