Min Cost To Make Two Strings Identical

Problem Overview

You may only delete characters, each with a fixed cost per string.

Intuition

You may only delete characters, each with a fixed cost per string. Characters that stay must form a common subsequence, so the cheapest plan keeps a longest common subsequence and deletes everything else.

Algorithm

1If needed, swap the strings so the shorter one sizes the DP row.
2Compute LCS length with two rolling arrays using the standard match or max skip recurrence.
3Let L be the LCS length after the DP finishes.
4Return (n - L) * costS1 + (m - L) * costS2.

Example Walkthrough

Input: s1 = "abcd", s2 = "acdb", costS1 = 10, costS2 = 20

1. An LCS such as "acd" has length 3.
2. Delete one character from s1 and one from s2.
3. Cost is 10 + 20 = 30.

Output: 30

Common Pitfalls

• You cannot insert or substitute; only deletions are allowed.
• Keeping any common subsequence works correctly, but a longest one minimizes deletions.
• Swap costs when you swap strings so each cost stays attached to its string.
• Rolling-row DP must not reuse a cell before the previous-row diagonal value is read.

Min Cost To Make Two Strings Identical.java

Java

// Approach: Deleting everything costs n*costS1 + m*costS2. Keeping an LCS of
// length L saves L*(costS1+costS2), so min cost = (n-L)*costS1 + (m-L)*costS2.
// Compute L with classic LCS DP, rolling one row so space is O(min(n,m)).
// Complexity: O(n*m) time, O(min(n,m)) extra space.
class Solution {
    public int findMinCost(String s1, String s2, int costS1, int costS2) {
        if (s1.length() < s2.length()) {
            String tmp = s1;
            s1 = s2;
            s2 = tmp;
            int c = costS1;
            costS1 = costS2;
            costS2 = c;
        }

        int n = s1.length(), m = s2.length();
        int[] prev = new int[m + 1];
        int[] curr = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    curr[j] = prev[j - 1] + 1;
                else
                    curr[j] = Math.max(prev[j], curr[j - 1]);
            }
            int[] swap = prev;
            prev = curr;
            curr = swap;
            // curr is reused; zeroing is unnecessary because every j is overwritten
        }

        int lcs = prev[m];
        return (n - lcs) * costS1 + (m - lcs) * costS2;
    }
}

Was this solution helpful?