2896. Apply Operations to Make Two Strings Equal LeetCode Solution

In this guide, you will get 2896. Apply Operations to Make Two Strings Equal LeetCode Solution with the best time and space complexity. The solution to Apply Operations to Make Two Strings Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Apply Operations to Make Two Strings Equal solution in C++
Apply Operations to Make Two Strings Equal solution in Java
Apply Operations to Make Two Strings Equal solution in Python
Additional Resources

2896. Apply Operations to Make Two Strings Equal LeetCode Solution image

Problem Statement of 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.

Example 1:

Input: s1 = “1100011000”, s2 = “0101001010”, x = 2
Output: 4
Explanation: We can do the following operations:
– Choose i = 3 and apply the second operation. The resulting string is s1 = “1101111000”.
– Choose i = 4 and apply the second operation. The resulting string is s1 = “1101001000”.
– Choose i = 0 and j = 8 and apply the first operation. The resulting string is s1 = “0101001010” = s2.
The total cost is 1 + 1 + 2 = 4. It can be shown that it is the minimum cost possible.

Example 2:

Input: s1 = “10110”, s2 = “00011”, x = 4
Output: -1
Explanation: It is not possible to make the two strings equal.

Constraints:

n == s1.length == s2.length
1 <= n, x <= 500
s1 and s2 consist only of the characters '0' and '1'.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2896. Apply Operations to Make Two Strings Equal LeetCode Solution in C++

class Solution {
 public:
  int minOperations(string s1, string s2, int x) {
    const vector<int> diffIndices = getDiffIndices(s1, s2);
    if (diffIndices.empty())
      return 0;
    // It's impossible to make two strings equal if there are an odd number of
    // differences.
    if (diffIndices.size() % 2 == 1)
      return -1;
    vector<double> mem(diffIndices.size(), -1.0);
    return minOperations(diffIndices, 0, x, mem);
  }

 private:
  // Returns the minimum cost to correct diffIndices[i..n).
  double minOperations(const vector<int>& diffIndices, int i, double x,
                       vector<double>& mem) {
    if (i == diffIndices.size())
      return 0;
    if (i == diffIndices.size() - 1)
      return x / 2;
    if (mem[i] != -1.0)
      return mem[i];
    return mem[i] = min(minOperations(diffIndices, i + 1, x, mem) + x / 2,
                        minOperations(diffIndices, i + 2, x, mem) +
                            diffIndices[i + 1] - diffIndices[i]);
  }

  vector<int> getDiffIndices(const string& s1, const string& s2) {
    vector<int> diffIndices;
    for (int i = 0; i < s1.length(); ++i)
      if (s1[i] != s2[i])
        diffIndices.push_back(i);
    return diffIndices;
  }
};
/* code provided by PROGIEZ */

2896. Apply Operations to Make Two Strings Equal LeetCode Solution in Java

class Solution {
  public int minOperations(String s1, String s2, int x) {
    List<Integer> diffIndices = getDiffIndices(s1, s2);
    if (diffIndices.isEmpty())
      return 0;
    // It's impossible to make two strings equal if there are odd number of
    // differences.
    if (diffIndices.size() % 2 == 1)
      return -1;
    Double[] mem = new Double[diffIndices.size()];
    return (int) minOperations(diffIndices, 0, x, mem);
  }

  private double minOperations(List<Integer> diffIndices, int i, double x, Double[] mem) {
    if (i == diffIndices.size())
      return 0;
    if (i == diffIndices.size() - 1)
      return x / 2;
    if (mem[i] != null)
      return mem[i];
    return mem[i] = Math.min(minOperations(diffIndices, i + 1, x, mem) + x / 2,
                             minOperations(diffIndices, i + 2, x, mem) + diffIndices.get(i + 1) -
                                 diffIndices.get(i));
  }

  private List<Integer> getDiffIndices(final String s1, final String s2) {
    List<Integer> diffIndices = new ArrayList<>();
    for (int i = 0; i < s1.length(); ++i)
      if (s1.charAt(i) != s2.charAt(i))
        diffIndices.add(i);
    return diffIndices;
  }
}
// code provided by PROGIEZ

2896. Apply Operations to Make Two Strings Equal LeetCode Solution in Python

class Solution:
  def minOperations(self, s1: str, s2: str, x: int) -> int:
    diffIndices = [i for i, (a, b) in enumerate(zip(s1, s2))
                   if a != b]
    if not diffIndices:
      return 0
    # It's impossible to make two strings equal if there are odd number of
    # differences.
    if len(diffIndices) & 1:
      return -1

    @functools.lru_cache(None)
    def dp(i: int) -> int:
      """Returns the minimum cost to correct diffIndices[i..n)."""
      if i == len(diffIndices):
        return 0
      if i == len(diffIndices) - 1:
        return x / 2
      return min(dp(i + 1) + x / 2,
                 dp(i + 2) + diffIndices[i + 1] - diffIndices[i])

    return int(dp(0))
 # code by PROGIEZ