LeetCode-in-Java
3980. Minimum Operations to Transform Binary String
Medium
You are given two binary strings s1 and s2 of the same length n.
You can perform the following operations on s1 any number of times, in any order:
- Choose an index
isuch thats1[i] == '0', and change it to'1'. - Choose an index
isuch that0 <= i < n - 1, and boths1[i]ands1[i + 1]are'1'. Change both characters to'0'.
Return the minimum number of operations required to make s1 equal to s2. If it is impossible, return -1.
Example 1:
Input: s1 = “11”, s2 = “00”
Output: 1
Explanation:
Change indices 0 and 1 from '1' to '0' in one operation, so "11" becomes "00". Thus, the answer is 1.
Example 2:
Input: s1 = “01”, s2 = “10”
Output: 3
Explanation:
- Change index 0 from
'0'to'1', so"01"becomes"11". - Change indices 0 and 1 from
'1'to'0', so"11"becomes"00". - Change index 0 from
'0'to'1', so"00"becomes"10". - Thus, the answer is 3.
Example 3:
Input: s1 = “1”, s2 = “0”
Output: -1
Explanation:
The first operation cannot change '1' to '0', and the second operation requires two adjacent characters. Therefore, it is impossible.
Constraints:
1 <= n == s1.length == s2.length <= 105s1ands2consist only of'0'and'1'.
Solution
public class Solution {
public int minOperations(String s1, String s2) {
int n = s1.length();
int sumDiff = 0;
int pairs = 0;
boolean isCovered = false;
for (int i = 0; i < n; i++) {
int diff = s1.charAt(i) - s2.charAt(i);
sumDiff += diff;
if (diff == 1 && !isCovered) {
if (i + 1 < n) {
pairs++;
isCovered = true;
} else {
if (i > 0) {
pairs++;
} else {
return -1;
}
}
} else {
isCovered = false;
}
}
return 3 * pairs - sumDiff;
}
}