top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Flip - Interviewbit Solution

Problem : Flip


Problem Description:

You are given a binary string(i.e. with characters 0 and 1) S consisting of characters S1, S2, …, SN. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters SL, SL+1, …, SR. 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.


For example,

S = 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].

Another example,

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

Solution:


2 Comments


Kumar Karan
Kumar Karan
Mar 21, 2022

Solution in Python -

Keep a running current sum , and +1 if we find "0" and -1 if we find "1" in the input string.

In case the current sum < 0 , reset current sum to 0.

Check if the current sum > maximum sum, then update the Left and Right indexes.


```

class Solution:

# @param A : string

# @return a list of integers

def flip(self, A):

n = len(A)

currSum, maxSum, L, R, currL = 0, -1, 0, 0, 0

allZeros = True

allOnes = True

for i in range(n):

if A[i]=='0':

currSum+=1

allOnes=False

else:

currSum-=1

allZeros=False


if currSum<0:

currSum=0

currL=i+1

continue

if currSum > maxSum:

maxSum = currSum

L = currL

R = i

Like

Kumar Karan
Kumar Karan
Mar 21, 2022

Solution in Python -


```

class Solution: # @param A : string # @return a list of integers def flip(self, A): n = len(A) currSum, maxSum, L, R, currL = 0, -1, 0, 0, 0 allZeros = True allOnes = True for i in range(n): if A[i]=='0': currSum+=1 allOnes=False else: currSum-=1 allZeros=False if currSum<0: currSum=0 currL=i+1 continue if currSum > maxSum: maxSum = currSum L = currL R = i if allZeros: L,R=1, n return [L, R] if allOnes: return [] L+=1 R+=1 return [L, R]

```

Like
bottom of page