The annotated classification values of the two datasets are represented using two binary strings, data1, and data2 where 0 represents one class and 1 represents another class.
In a single operation, the rightmost data point of data1 can be removed or the leftmost data point of data2 can be removed.
Given data1 and data2, find the minimum number of operations required such that after merging the two data sets, the total number of 0s is equal to the total number of 1s.
Note: The two datasets do not need to be of the same size at the time of merging.
The only requirement is that the combined dataset must contain an equal number of 0s and 1s.
Method Signature
int minOperationsToUnbias(int n, String data1, String data2)Parameters
int n: The initial size of the datasetsString data1: The classification values of the first datasetString data2: The classification values of the second dataset
Returns
int: The minimum operations required so that the total number of 1s is equal to the total number of 0s.
Constraints
1 ≤ n ≤ 105
Examples
Example 0
minOperationsToUnbias(2, "01", "11") => 2Explanation
It is optimal to remove both the 1s from the second data set or remove the last 1 from data1 and first 1 from data2. Both require two operations finally after merging the data the number of 0s and 1s will be equal to 1.
Example 1
minOperationsToUnbias(6, "111001", "010110") => 6Explanation
In the first operation, remove the last 1 from data1, and in five operations, remove the first five characters of data2. Finally, data1 = "11100" and data2 = "0".
Example 2
minOperationsToUnbias(1, "0", "1") => 0The merged dataset already has one 0 and one 1, so it is already unbiased.
Example 3
minOperationsToUnbias(3, "111", "11") => 5There are no 0s at all, so the only way to make counts equal is to remove all characters from both strings (empty merged dataset has equal zeros and ones).
Example 4
minOperationsToUnbias(4, "0101", "0000") => 2Remove two leading 0s from data2 (two operations). Then the merged totals can be balanced.