Flip


  • 3

    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.

    You 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.

    Notes:

    • Pair (a, b) is lexicographically smaller than pair (c, d) if a < c or, if a == b, then 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 [].


  • 0
    This post is deleted!

  • 1

    Interesting problem~

    Analysis

    The string must can be separated into several segments:

    [0*][1+][0+][1+] ... [1+][0*]
    

    If we choose L and R to be the answer, we are sure about the following truth:

    1. count(0) - count(1) must be the largest among all choice of L and R.
    2. L must be the start of one of [0+] or [0*] segment.
    3. R must be the end of one of [0+] or [0*] segment.

    We start counting from the start of the string with the iteration of each segment:

    1. init a variable, say value to be 0, and a ptr which points to 0
    2. add x to value if the segment has x '0's
    3. minus x from value if the segment has x '1's
    4. every time the value becomes smaller than 0, reset it to be 0. Also set ptr to be the current position
    5. if value is larger than it ever had been, record the current value and the corresponding L and R.

    Time complexity: O(n)
    Space complexity: O(1)

    Simple python code
    def flip(line):
        value, max_value, ptr, ret = 0, 0, 0, []
        for i in range(len(line)):
            value += (line[i] == '0') * 2 - 1
            if value < 0:
                value, ptr = 0, i + 1
            elif value > max_value:
                max_value, ret = value, [ptr, i]
        return ret
    
    Note

    I wrote this code directly on the edit panel, so it may have some flaw. I just aimed at my thoughts. Thanks.


  • 0

    By the way, as a reference, the following problem looks similar to this one which is also very interesting~
    https://code.google.com/codejam/contest/6254486/dashboard#s=p1


  • 0
    This post is deleted!

  • 0

    @xidui , could you tell me for example [0011000110] what will be the result with your approach.

    I follow your reasoning.
    00 -val =2
    11 - val = 0
    000 - val < 0 , ptr = i
    11 - val = 2
    00 val = 0
    It seems to me that with the code above max_val will be 2, but I think that max_val should be 3 , ret should be [4 - 6]
    Thanks


  • 0

    @elmirap
    I think you may have some misunderstanding at 000 - val, it is three and larger than 2.
    So after that, max_value is 3 and ret is [0, 6]

    The code:

    value += (line[i] == '0') * 2 - 1
    

    means add one when '0' and minus one when '1'


  • 0

    @elmirap
    I think [0,6] should be the answer rather than [4,6] according to the lexicographically order.


  • 0

    @xidui could be. Yes, right...


  • 1

    Here is dp solution.It used Kadane algolithm for maximum sum subarray. The idea is related to fact that when 0 is flipped, +1 is added to the number of 1's, when 1 is flipped -1 is substracted from the number of 1's. We try to maximize total gain from flip of some range [i,j].The algorithm search the max sum subarray of array which contains what is the gain when give index is flipped.

    int[] getFlipRange(String str) {
        if (str.length() == 0)
            return new int[]{};		 
        boolean zero = false;
        int gain[] = new int[str.length()];
        for (int i = 0; i< str.length(); i++) {		        
               gain[i] = (str.charAt(i) == '1') ? -1 : 1;
           if (str.charAt(i) == '0') {
                   zero = true; 
               }
        }
        if(!zero)
            return new int[]{};   
        int l = 0;
        int r = str.length() - 1;
        int maxSum = 0;
        int curSum = 0;
        int currL = 0;
        int currR = 0;
        for (int i =  0; i < gain.length; i++) {
            if (curSum + gain[i] >= 0) {
                curSum += gain[i];
                currR = i;
            }
            else {
                curSum = 0;	
                currL = i + 1;
            }
            if (curSum > maxSum) {
                maxSum = curSum;	
                l = currL;
                r = currR;
            }		       
        }
        return new int[]{l + 1, r + 1};
    }
    

  • 0

    @xidui can we solve https://code.google.com/codejam/contest/6254486/dashboard#s=p1 with greedy techniques? Each time I get all pancakes with the same face from top and flip them till all pancakes +
    For example I have 3 pancakes :
    /+
    /+
    /-
    I suggest first to flip the first two :
    /-
    /-
    /-
    Then to flip the three.
    /+
    /+
    /+

    Another example :
    .-
    .-
    .+
    .-

    1. step
      .+
      .+
      .+
      .-
    2. step
      .-
      .-
      .-
      .-
    3. step
      .+
      .+
      .+
      .+

  • 1

    @elmirap
    Yeah, I think we can do it with greedy and your approach works.

    We need to find how many jumps in the string(A jump means + change to - or - change to +).

    The answer is the count of jumps(If the first is -, answer should plus one).

    and my c++ code:

    #include <iostream>
    using namespace std;
    
    int main(int argc, const char * argv[]) {
        int T, t = 0;
        cin >> T;
        while (t++ != T){
            string s;
            cin >> s;
            int count = 0;
            for (int i = 1; i < s.length(); ++i) {
                if (s[i] != s[i - 1]) ++count;
            }
            if (s[s.length() - 1] == '-') count++;
            cout << "Case #" << t << ": " << count << endl;
        }
        return 0;
    }
    

  • 0
    T

    Correct me if I'm Wrong .

    void flip(string s)
    {
        int len = s.size();
        if(len==0)  { cout<<"Empty String"<<endl ; return ; }
        int ans[2] = {-1 , -1} ;
        int c = 0 , sum ;
        for(int i=0;i<len;i++)  if(s[i]=='1')   c++;
        sum = c ;
        for(int i=0;i<len;i++)
        {
            int t = c ;
            for(int j=i;j<len;j++)
            {
                if(s[j]=='0')
                {
                    t++;
                    if(t>sum)
                    {
                        sum = t ;
                        ans[0] = i+1 ; ans[1] = j+1 ;
                    }
                }
                else  t--;
            }
        }
        cout<<ans[0]<<" "<<ans[1]<<endl;
    }
    

  • 0
    A

    @xidui What will be output of this case?
    011011
    I think [4,4], as changing only 0 at (4,4) will result in maximum 1's.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.