DWW19C - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ankush Khanna

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given two strings A and B, determine the minimum cost of converting A into B when adding a new character into A is a unit cost operation, and deleting and swapping (or ordering) characters from/in A are free operations.

QUICK EXPLANATION:

  • Create character count arrays for both the strings.
  • If the character count of a character in B is more than that of A, then add the count difference to the answer.

EXPLANATION:

First of all we should realize the fact that ordering characters in A after everything is done will never be a problem or add to the cost. Also deleting characters from A will never be a problem. Therefore, we should only focus on adding those characters which are missing in A when compared to B.

Now, the most important step is to create two character count arrays for strings A and B respectively. Though this can also be done using a single character count array by adding the count for A and subtracting the count for B. But in this editorial I am discussing about keeping two different character count arrays for the purpose of simplicity.

For optimal construction of B from A, there are two things that we should keep in mind:

  • We should always add only those characters to A which are deficit in A as compared to B till the count of that particular character in A becomes equal to that of B. The characters which are more in A as compared to B will never contribute to the answer. The simple reason for that is we can drop the extra ones in A for free, and they’re not required to construct the string B.

  • We should never delete a character which is deficit in A as compared to B. Because, in case we delete it for free, then we’ll have to add it back anyhow for an extra unit cost. So, it is optimal never to delete such a character from A.

So, in all, we should always add only those characters which are deficit in A as compared to B and never delete them. This is the only strategy to get the minimum cost of addition of characters to string A to from string B and hence our answer.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        string a, b;
        cin >> a >> b;
        vector<int> c_a(26), c_b(26);
        for (char c : a) {
            c_a[c - 'A']++;
        }
        for (char c : b) {
            c_b[c - 'A']++;
        }
        int cost = 0;
        for (int i = 0; i < 26; i++) {
            if (c_b[i] > c_a[i]) {
                cost += c_b[i] - c_a[i];
            }
        }
        cout << cost << '\n';
    }
    return 0;
}

COMPLEXITY:

Time complexity: O(|A| + |B|) per test
Space Complexity: O(1) auxiliary space per test

Feel free to share your approach. If you have any queries, they are always welcome.