Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3033. Apply Operations to Make Two Strings Equal

My accepted Python solution to LeetCode problem 3033, Apply Operations to Make Two Strings Equal, running in 3ms.

  • Difficulty: Medium
  • Python
  • Runtime 3ms
  • Memory 17.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 3ms, memory 17.4MB, accepted 2026-01-02.

python
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        n = len(s1)
        # Find positions where s1 != s2
        diff = [i for i in range(n) if s1[i] != s2[i]]
        
        if len(diff) == 0:
            return 0
        if len(diff) % 2 == 1:
            return -1  # Can't make equal with odd differences
        
        m = len(diff)
        
        # DP: dp[i] = min cost to handle first i differences
        # For each pair of consecutive diffs, we can either:
        # 1. Use operation 2 repeatedly (cost = diff[i+1] - diff[i])
        # 2. Use operation 1 to pair with some other diff (cost = x)
        
        # Better formulation:
        # dp[i] = min cost to resolve diffs[0..i-1]
        # For diff[i], we can pair it with:
        # - diff[i-1] using adjacent flips: cost = diff[i] - diff[i-1]
        # - Some earlier diff using operation 1: cost = x (but need to track)
        
        # Let's use: dp[i][0] = min cost, no unpaired diff
        #           dp[i][1] = min cost, one unpaired diff at position i
        
        INF = float('inf')
        # dp[i] = min cost to handle all diffs up to index i, with all paired
        # We process pairs greedily or use DP
        
        # Alternative: interval DP or think of it as matching
        # Each diff must be paired. Pairing (i, j) costs min(diff[j]-diff[i], x)
        # We want minimum weight perfect matching on diffs
        
        # For optimal matching, consecutive pairs are always optimal
        # dp[i] = min cost to match first i diffs (i must be even)
        
        dp = [INF] * (m + 1)
        dp[0] = 0
        
        # Also track: dp2[i] = min cost if we have one "free" operation 1 waiting
        # That is, we used x/2 to mark one diff as needing a partner
        dp2 = [INF] * (m + 1)
        
        for i in range(m):
            # Option 1: Pair diff[i] with diff[i+1] using adjacent operations
            if i + 1 < m:
                cost = diff[i + 1] - diff[i]
                dp[i + 2] = min(dp[i + 2], dp[i] + cost)
            
            # Option 2: Use operation 1 - pay x, pair diff[i] with some later diff
            # We split: pay x/2 now for diff[i], x/2 later for partner
            # Actually, let's track half-used operation 1
            dp2[i + 1] = min(dp2[i + 1], dp[i] + x)  # start new op1 at diff[i]
            
            # If we have a pending half-op1, complete it
            if dp2[i] < INF:
                dp[i + 1] = min(dp[i + 1], dp2[i])  # complete pairing
                # Or pair with next using adjacent
                if i + 1 < m:
                    dp2[i + 2] = min(dp2[i + 2], dp2[i] + (diff[i + 1] - diff[i]))
        
        return dp[m] if dp[m] < INF else -1

Source