3980. Minimum Operations to Transform Binary String

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 i such that s1[i] == '0', and change it to '1'.
• Choose an index i such that 0 <= i < n - 1, and both s1[i] and s1[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.

class Solution {
public:
    int minOperations(string s1, string s2) {
        int n = s1.size();
        const int INF = 1e9;

        vector<vector<int>> dp(n + 1, vector<int>(2, INF));
        dp[0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int zero = 0; zero < 2; zero++) {
                if (dp[i][zero] == INF) continue;

                int cur = zero ? 0 : s1[i] - '0';
                int target = s2[i] - '0';

                if (cur == target) {
                    dp[i + 1][0] = min(dp[i + 1][0], dp[i][zero]);
                }

                if (cur == 0 and target == 1) {
                    dp[i + 1][0] = min(dp[i + 1][0], dp[i][zero] + 1);
                }

                if (i + 1 < n) {
                    int cost = 1;

                    if (cur == 0) cost++;
                    if (s1[i + 1] == '0') cost++;

                    if (target == 1) cost++;

                    dp[i + 1][1] = min(dp[i + 1][1], dp[i][zero] + cost);
                }
            }
        }

        return dp[n][0] == INF ? -1 : dp[n][0];
    }
};