2896. Apply Operations to Make Two Strings Equal

You are given two 0-indexed binary strings s1 and s2, both of length n, and a positive integer x.

You can perform any of the following operations on the string s1 any number of times:

• Choose two indices i and j, and flip both s1[i] and s1[j]. The cost of this operation is x.
• Choose an index i such that i < n - 1 and flip both s1[i] and s1[i + 1]. The cost of this operation is 1.

Return the minimum cost needed to make the strings s1 and s2 equal, or return -1 if it is impossible.

Note that flipping a character means changing it from 0 to 1 or vice-versa.

class Solution {
public:
    int minOperations(string s1, string s2, int x) {
        vector<int> p;
        for(int i = 0; i < s1.length(); i++) {
            if(s1[i] != s2[i]) p.push_back(i);
        }
        if(p.size() & 1) return -1;
        vector<vector<long long>> dp(p.size() + 2, vector<long long>(p.size() + 2, 1e9));
        dp[0][0] = 0;
        for(int i = 0; i < p.size(); i++) {
            for(int j = 0; j <= p.size(); j++) {
                if(j == 0) {
                    dp[i+1][1] = min(dp[i+1][1], dp[i][j]);
                } else {
                    dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j] + x);
                }
                if(i + 1 < p.size()) {
                    dp[i+2][j] = min(dp[i+2][j], dp[i][j] + min(p[i+1] - p[i], x));
                }
            }
        }
        return dp[p.size()][0];
    }
};