Day 78: Complement

/*
Complement

You are given a binary string str. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and complement the characters between L and R i.e strL, strL+1, …, strR. By complement, we mean change character 0 to 1 and vice-versa.

You task is to perform ATMOST one operation such that in final string number of 1s is maximised. If there is no need to completement, i.e., string contains all 1s, return -1. Else, return the two values denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.

Example 1:

Input:
N = 3
str = "111"
Output: -1
Explanation: As all characters are '1', 
so don't need to complement any.
Example 2:

Input:
N = 2
str = "01"
Output: 1 1
Explanation: After complementing [1, 1] 
the string becomes "11".
Your Task:
You don't need to read input or print anything. Complete the function findRange() which takes the string str and the size of the string, n, as input parameters and returns an array of length 2 or 1 representing the answer. You don't to print answer or take inputs.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 105
Str is a binary string i.e. contains only '0' and '1'.
*/

//{ Driver Code Starts
// Initial Template for Java

import java.io.*;
import java.util.*;

class GFG {
    // Driver code
    public static void main(String[] args) throws Exception {
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            String str = br.readLine().trim();

            Vector<Integer> ans = new Solve().findRange(str, n);
            if (ans.size() == 1) {
                System.out.println(ans.get(0));
            } else {
                System.out.println(ans.get(0) + " " + ans.get(1));
            }
        }
    }
}

// } Driver Code Ends


// User function Template for Java

class Solve {

    Vector<Integer> findRange(String str, int n) {
        Vector<Integer> vector  = new Vector<Integer>();
        int count =0;
        for(int i=0; i< n; i++ ) {
            if(str.charAt(i) == '1') count++;
        }
        if(count == n) {
            vector.add(-1);
            return vector;
        }
        int left = 0, right = 0, start = 0, sum = 0, maxi = Integer.MIN_VALUE;
        for(int i=0; i< n; i++){
            char c = str.charAt(i);
            if( c == '1'){
                sum -= 1;
            }else {
                sum += 1;
            }
            if(sum  > maxi){
                maxi = sum;
                left = start;
                right = i;
            }
            if(sum < 0){
                sum = 0;
                start = i+1;
            }
        }
        vector.add(left+1);
        vector.add(right+1);
        return vector;
    }
}