An engineer is working to build an integrated binary circuit that takes input a binary string s. A binary string consisting of only 0s and 1s can be segregated by moving all the 1s towards the end of the string. For example, the string "01010", after segregation becomes "00011".
In a single operation, any "1" from the binary string can be chosen and moved to the right until it reaches the end of the string or another "1". The cost of the operation is 1 + the number of places the one is moved. For example, in the string "100010", the first one can be moved three places to the right in cost 4. Note that it is mandatory to move a 1 to the maximum possible position to the right.
Given a binary string s, find the maximum number of operations possible to segregate the given string.
Function Description
Complete the function getMaxCost in the editor.
getMaxCost has the following parameter:
string s: The given binary string
Returns
long integer: the maximum possible cost for segregating the given string
Example 1:
Input: s = "110100"
Output: 13
Explanation:The final string should be "000111". The optimal way to maximize the number of operations will be:
- Swap the second and the third characters at a cost of 2. The string becomes "101100".
- Swap the first and the second characters at a cost of 2. The string becomes "011100".
- Now, we move each one to the end i.e. moving 2 places at a cost of 3 each.
The total cost of segregation is 2 + 2 + 3 * 3 = 13. Hence the answer is 13.
- 1 ≤ length of
s≤ 105 - Each character of the given string is either '0' or '1'.
input:
output: