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.
SOLUTION
The idea is to convert the zeroes to 1 and ones to -1. When 0 will be flipped, we will gain a 1. When 1 will be flipped, we will lose 1.
Then the problem changes to finding the maximum sum subarray’s start and end position. We can tweak Kadane’s Algorithm to do this by tracking the L and R for the maximum sub subarray.
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class Solution {
public int[] flip(String A) {
int n = A.length();
int[] arr = new int[n];
// Converting the input string into an array of 1s and -1s
for(int i=0; i<n; i++){
if(A.charAt(i) == '0'){
arr[i] = 1;
} else {
arr[i] = -1;
}
}
int maxSum = 0;
int currentSum = 0;
int L = 0;
int R = 0;
int[] ans = new int[]{-1, -1};
boolean foundOne = false; // Flag to check if there's at least one '1' in the input string
for(int i=0; i<n; i++){
if(arr[i] == 1) foundOne = true; // Set the flag to true if encountering a '1'
currentSum += arr[i]; // Add the current element to the current sum
if(currentSum > maxSum){
maxSum = currentSum; // Update the maximum sum found so far
R = i; // Update the ending index of the potential subarray
// Update the answer array with the potential subarray indices
ans[0] = L+1;
ans[1] = R+1;
}
if(currentSum < 0){
currentSum = 0; // Reset the current sum if it becomes negative
//IMPORTANT: when the currentSum becomes 0, we need to discard the previous subarray and start checking from the next index
L = i + 1; // Move the starting index of the potential subarray to the next index
}
}
if(!foundOne){ // If no '1' was found in the input array, return an empty array
return new int[]{};
}
return ans;
}
}