# Flip: Interview Bit

Problem Description

You are given a binary string A(i.e. with characters 0 and 1) consisting of characters A1, A2, ..., AN. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters AL, AL+1, ..., AR. By flipping, we mean change character 0 to 1 and vice-versa.

Your aim is to perform ATMOST one operation such that in final string number of 1s is maximised.

If you don't want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.

NOTE: Pair (a, b) is lexicographically smaller than pair (c, d) if a < c or, if a == c and b < d.

Input Format

First and only argument is a string A.

Output Format

Return an array of integers denoting the answer.

Example Input

Input 1:

A = "010"

Input 2:

A = "111"

Example Output

Output 1:

[1, 1]

Output 2:

[]

Example Explanation

Explanation 1:

A = "010"Pair of [L, R] | Final string ____________

|__________ [1 1] | "110" [1 2] | "100" [1 3] | "101" [2 2] | "000" [2 3] | "001"We see that two pairs [1, 1] and [1, 3] give same number of 1s in final string. So, we return [1, 1].

Explanation 2:

No operation can give us more than three 1s in final string. So, we return empty array [].

vector<int> Solution::flip(string s) {// sum to store current sum till nowint sum=0;// mx to store the maximum sum, in the starting it can be -1 of INT_MINint mx=-1;// x to store the starting of the subarry as it is one indexed to we keep it as 1int x=1;// ans vector which we will returnvector<int>ans(2);//iterating in the given stringfor(int i=0; i<s.length(); i++){// if the current char is 0 we increase the sumif(s[i]=='0')sum++;// else we decrease the sumelse sum--;// if the sum is negative means we have more nubmer of ones now so we will reset sum and x// x is i+2 because we are assuming 1 indexed array and now our subarry starts from the next elementif(sum<0){x=i+2;sum=0;continue;}// if the number of 0 is greater than one we update our answer and maximum sumif(sum>mx){ans[0]=x;ans[1]=i+1;mx=sum;}}// if the string has only 0if(count(s.begin(),s.end(),'0')==s.length())return {1,s.length()};// if the string has only 1if(count(s.begin(),s.end(),'1')==s.length())return {};return ans;}

## 0 Comments

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.