Reduce price to type Binary String by swapping pairs or reversing prefix at most as soon as

Given binary string S of size N, the duty is to attenuate price to type the binary string utilizing the next operations:

• Operation-1: Take any two indices i and j such that 0 ≤ i, j < N and swap S_i and S_j. This operation is carried out any variety of occasions. Its price is 1.
• Operation-2: Take any prefix of size i, the place 1 ≤ i, j ≤ N, and reverse this prefix of the binary string. It may be carried out at most as soon as and its price is 0.

Examples:

Enter: S = “10100” 
Output: 1 

Clarification: Carry out an operation 1 by selecting i = 1 and j=2. 
So 10100 turns into 11000, and price is 1. 
Then, carry out an operation 2, by selecting i = 5,  
which suggests reverse all the string, and so from 1100, we get 00011.
This operation price is 0.
So complete price is 0 + 1 = 1.

Enter: S = “101”

Output: 0

Strategy: The issue will be solved primarily based on the next remark: 

• Be aware that the operations can all the time be reordered in order that the prefix reverse operation is carried out first – if any swaps are made earlier than the reverse operation, these swaps will be carried out (on perhaps completely different positions) after reversing the prefix.
• So, repair size of the prefix to reverse, say i(0 ≤ i ≤ N) and calculate the minimal variety of swaps required to type the string now.

Primarily based on the above observations, this concept will be fashioned:

As, price of operation 2 is 0, simply type the binary string with both 0s in first or 1s in first and wich ever prices much less could be the reply.

Comply with the steps talked about under to implement the above concept:

• Say there are x 0s and y 1s. So all the primary x characters shall be 0 and the final y characters shall be 1.
• If any of the primary x characters is already a zero, it’s in place and nothing must be accomplished.
• If any of the primary x characters is a one, it must be swapped out with a zero. This may be accomplished in precisely one transfer since every one among the many first x characters will correspond to a one among the many final y characters.
• Create a prefix array to retailer the variety of 0s until i^th index.
• For every index test the worth of (pref[n]-pref[n-ones+i]+pref[i]) the place ones is the variety of 1s within the string. The minimal amongst these is the reply.

Beneath is the implementation of the above method.

Time Complexity: O(N) 
Auxiliary House: O(1)