Minimum Cost To Convert A String To Another By Replacing Blanks In C++

Minimum Cost To Convert A String To Another By Replacing Blanks In C++ Let’s see through an example.

Given two strings, s1 and s2, both of length N, with lower-case alphabets. The strings s1 and s2 may include some blanks at first, thus the goal is to discover the fewest operations possible to convert s1 to s2.

1. If there are any blanks, they should be filled in with any character that costs zero.
2. Any consonant can replace any vowel in the string, and any consonant can be replaced by any vowel that costs 1.

Example:

Input: s1 = “g_e_s”, s2 = “ge_ks”
Output: 1
Explanation: Replacing blanks with ‘e’, the strings become  s1= “geees”, s2 = “geeks”
In the 3rd index of s1 convert e -> k which costs only 1 operation. 

Input: s1 = “abcd”, s2 = “aeca”
Output: 2

Approach:

Because there are only 26 lower case characters, any blanks in the strings can be filled with one of these characters, and the cost of converting string s1 to s2 is kept to a minimum. If one of the string’s characters is a vowel and the other is a consonant or vice versa, transforming one character costs only one unit. Consonant -> vowel -> consonant (cost = 2) or vowel -> consonant -> vowel (cost = 2).

Follow these steps to solve the above problem:

• If both the lengths of the strings are not equal return -1.
• Initialize n with the length and res as INT_MAX.
• Now iterate through each of the 26 characters.
• Initialize the variable ops = 0 to store the costs required.
• Traverse from the range [0, n) and check if there is a blank in any of the strings.
• If there is a blank initialize the chars c1 and c2 to store the modified characters.
• If both the chars c1 == c2 (the character after replacing the blank) no operations are required.
• Else if both are vowels or consonants it requires 2 operations else it requires only 1 operation add it to the ops variable.
• After the traversal store the minimum operations in the res (min(ops, res)).
• Print the result res.

Below is the implementation of the above approach:

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

// Function to check whether
// a character is vowel or not
bool isVowel(char c)
{
	return (c == 'a' || c == 'e' || c == 'i'
			|| c == 'o' || c == 'u');
}

// Function to calculate minimum cost
void minCost(string s1, string s2)
{
	// If both the lengths are not equal
	if (s1.length() != s2.length()) {
		cout << -1 << endl;
		return;
	}

	int n = s1.length();

	// Initialize res with max value
	int res = INT_MAX;

	// Iterate through every character
	// and check the minimum cost by
	// replacing the blank by all letters
	for (char c = 'a'; c <= 'z'; c++) {

		// Initialize ops to check
		// the cost required by replacing
		// each char c
		int ops = 0;
		for (int i = 0; i < n; i++) {

			// If it is blank reolace with c
			char c1 = s1[i] == '_' ? c : s1[i];
			char c2 = s2[i] == '_' ? c : s2[i];

			// If both are equal no ops required
			if (c1 == c2)
				continue;
			else {

				// If both are vowels or onsonants
				// it requires cost as two
				// vowel->consonant ->vowel
				// and vice versa
				// Else 1 operation
				ops
					= ops
					+ (isVowel(s1[i]) != isVowel(s2[i])
							? 2
							: 1);
			}
		}

		// Take the minimum
		if (ops < res) {
			res = ops;
		}
	}

	// Print the result
	cout << res << endl;
}

// Driver code
int main()
{
	// Initialize the strings
	string s1 = "g_e_s", s2 = "ge_ks";

	// Function call
	minCost(s1, s2);

	return 0;
}

Output:

1

Time Complexity: O(26* N)
Space Complexity: O(1)