Minimize Operations To Make One String Contain Only Characters From Other String In C++

Minimize Operations To Make One String Contain Only Characters From Other String In C++, How to evaluate let’s see.

Given two strings S1 and S2, both of which contain only lower case English alphabets, the goal is to reduce the number of operations required to make S1 contain only characters from S2, where any character of S1 can be converted to any other letter in each operation, and the cost of the operation is the difference between those two letters.

Examples:

Input: S1 = “abc”, S2 = “ad”
Output: 2

Explanation:
The first character of S1 doesn’t required to change, as character ‘a’ also present in S2.

The second character of S1 can be changed to ‘a’ as to make it ‘a’ needs 1 operation and to make it to ‘d’ needs 2 operations.

The third character of S1 can be changed to ‘d’ as to make it ‘a’ needs 2 operations and to make it to ‘d’ needs 1 operation.

So the minimum number of operations to make the string “abc” to “aad” it needs 2 operations.

Input: S1 = “aaa”, S2 = “a”
Output: 0
Explanation: S1 contains characters only present in S2.

Approach:

The goal is to determine the smallest number of operations required to convert each character in S1 to any of the characters in S2 that are the closest match. To address the problem, follow the instructions below:

Set a variable, say minOpr, to 0 to keep track of the very minimum of operations required.

Using the variable i iterate across the range [0, N1) and conduct the following steps:

Initialize a variable, say minOpr as 0 that stores the minimum number of operations required.
Iterate over the range [0, N1) using the variable i and perform the following steps:
- Check if the character S1[i] is present in the S2. If not present then continue with the iteration.
- Iterate over the range [0, 26) using the variable j.
  - Check if S1[i] greater than S2[j] then find minimum of curMinOpr, (S1[i] – S2[j]) and (26 – (S1[i]-‘a’) + (S2[j] – ‘a’)) and store the value in curMinOpr.
  - Else, find minimum of curMinOpr, (S2[j] – S1[i]) and ((S1[i] – ‘a’) + (26 – (S2[j] – ‘a’))) and store the value in curMinOpr.
- Update the value of minOpr to minOpr += curMinOpr.
Finally, print the value of minOpr.

Below is the implementation of the above approach:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to find the minimum number of
// operations required to make string S1
// contains only characters from the string S2
void minOperations(string S1, string S2,
				int N1, int N2)
{
	// Stores the minimum of operations
	// required
	int minOpr = 0;

	for (int i = 0; i < N1; i++) {

		// Check character S1[i] is not
		// present in S2
		if (S2.find(S1[i]) != string::npos) {
			continue;
		}

		// Stores the minimum operations required
		// for the current character S1[i]
		int curMinOpr = INT_MAX;

		for (int j = 0; j < N2; j++) {

			// Check S1[i] alphabet is greater
			// than the S2[j] alphabet
			if (S1[i] > S2[j]) {

				// Find the minimum operations
				// required to make the
				// character S1[i] to S2[j]
				curMinOpr
					= min(curMinOpr,
						(min(S1[i] - S2[j],
							26 - (S1[i] - 'a')
								+ (S2[j] - 'a'))));
			}
			else {

				// Find the minimum operations
				// required to make the
				// character S1[i] to S2[j]
				curMinOpr = min(
					curMinOpr,
					(min(S2[j] - S1[i],
						(S1[i] - 'a')
							+ (26 - (S2[j] - 'a')))));
			}
		}

		// Update the value of minOpr
		minOpr += curMinOpr;
	}

	// Print the value of minOpr
	cout << minOpr << endl;
}

// Driver code
int main()
{
	string S1 = "abc", S2 = "ad";
	int N1 = S1.length(), N2 = S2.length();

	minOperations(S1, S2, N1, N2);

	return 0;
}

Output:

Time Complexity: O(N₁ * N₂) where N₁ and N₂ are the size of S1 and S2 respectively
Auxiliary Space: O(1)