Flip - The Coding Shala

Home >> Interview Questions >> Flip

Flip InterviewBit Solution

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 to change the character 0 to 1 and vice-versa.
Your aim is to perform ATMOST one operation such that in final string number of 1's is maximized. 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.
Flip InterviewBit Java Program - The Coding Shala
Notes:
  • 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 2] | 100
[1 1] | 110 [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

First, make the array of 1 and -1 then find the left and right indexes within these sum of the array will be maximum.

Java Code::
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public ArrayList<Integer> flip(String A) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        int n = A.length();
        int arr[] = new int[n];
        for(int i=0;i<n;i++){
            if(A.charAt(i)=='0') arr[i] = 1;
            else arr[i] = -1;
        }
        int temp_start = 0, temp_end = 0, start = -1, end = -1, move_start = 0;
        for(int i = 0;i<n;i++){
            if(temp_end+arr[i]<0){
                move_start = i+1;
                temp_end = 0;
            }else temp_end += arr[i];
            if(temp_end > temp_start){
                temp_start = temp_end;
                start = move_start;
                end = i;
            }
        }
        if(start == -1) return ans;
        ans.add(start+1);
        ans.add(end+1);
        return ans;
    }
}



Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

  1. If you have any doubts, you may watch this video by alGOds for the explanation and dry run of the algorithm.
    Link : https://youtu.be/cLVpE5q_-DE

    ReplyDelete

Post a Comment

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala