Skip to content

2896. Apply Operations to Make Two Strings Equal 👍

Approach 1: Top-down

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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))

Approach 2: Bottom-up 1D DP

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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> dp(diffIndices.size() + 1, DBL_MAX);
    dp.back() = 0;
    dp[diffIndices.size() - 1] = x / 2.0;

    for (int i = diffIndices.size() - 2; i >= 0; --i)
      dp[i] = min(dp[i + 1] + x / 2.0,
                  dp[i + 2] + diffIndices[i + 1] - diffIndices[i]);

    return dp[0];
  }

 private:
  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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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[] dp = new double[diffIndices.size() + 1];
    Arrays.fill(dp, Double.MAX_VALUE);
    dp[diffIndices.size()] = 0;
    dp[diffIndices.size() - 1] = x / 2.0;

    for (int i = diffIndices.size() - 2; i >= 0; --i)
      dp[i] = Math.min(dp[i + 1] + x / 2.0, //
                       dp[i + 2] + diffIndices.get(i + 1) - diffIndices.get(i));

    return (int) dp[0];
  }

  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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

    # dp[i] := the minimum cost to correct diffIndices[i:]
    dp = [math.inf] * len(diffIndices) + [0]
    dp[-2] = x / 2

    for i in reversed(range(len(diffIndices) - 1)):
      dp[i] = min(dp[i + 1] + x / 2,
                  dp[i + 2] + diffIndices[i + 1] - diffIndices[i])

    return int(dp[0])

Approach 3: Bottom-up $O(1)$ DP

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;

    double dp = 0;
    double dpNext = x / 2.0;
    double dpNextNext = 0;

    for (int i = diffIndices.size() - 2; i >= 0; --i) {
      dp = min(dpNext + x / 2.0,
               dpNextNext + diffIndices[i + 1] - diffIndices[i]);
      dpNextNext = dpNext;
      dpNext = dp;
    }

    return dp;
  }

 private:
  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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 dp = 0;
    double dpNext = x / 2.0;
    double dpNextNext = 0;

    for (int i = diffIndices.size() - 2; i >= 0; --i) {
      dp = Math.min(dpNext + x / 2.0, //
                    dpNextNext + diffIndices.get(i + 1) - diffIndices.get(i));
      dpNextNext = dpNext;
      dpNext = dp;
    }

    return (int) dp;
  }

  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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

    #         dp := the minimum cost to correct diffIndices[i:]
    #     dpNext := the minimum cost to correct diffIndices[i + 1:]
    # dpNextNext := the minimum cost to correct diffIndices[i + 2:]
    dpNext = x / 2
    dpNextNext = 0

    for i in reversed(range(len(diffIndices) - 1)):
      dp = min(dpNext + x / 2,
               dpNextNext + diffIndices[i + 1] - diffIndices[i])
      dpNextNext = dpNext
      dpNext = dp

    return int(dp)