Minimum operations to convert String A to String B
Given two strings consisting of lowercase alphabets A and B, both of the same length. Each character of both the strings is either a lowercase letter or a question mark β?β. The task is to find the minimum number of operations required to convert A to B, in one operation you can choose an index i, if A[i] is a vowel convert it to a consonant, and if A[i] is a consonant convert it to vowel. Prior to performing any operation you need to replace each occurrence of β?β in both strings A and B with the same lowercase letter.
Note: For conversion from a consonant to a consonant, we need two steps: consonant->vowel->consonant. The same shall be true for vowel-to-vowel conversion.
Examples:
Input: A: βabcd?β, B: βacxe?β
Output: 1
Explanation: We can replace the ? character by any alphabet and the number of operations will be same.Input: A = βab?c?β, B = βaeg?kβ
Output: 4
Explanation: If each instance of ? is replaced by βuβ . Then A = βab?c?β, B = βaeg?kβ. The number of operations required is 4 which the least one can get.
Approach: To solve the problem follow the below idea:
The number of characters in the lowercase English alphabet is 26. This suggests that we can first replace each instance of β?β in both the strings with each alphabet (a β z) at one time. Now we have two newly complete strings without any occurrence of β?β we can calculate the number of operations it would take to convert A to B. Each character when placed in the location of β?β for both the strings gives some number of operations. The minimum number of these operations gives the final answer.
Illustration:
It is clear from the problem statement itself that once we replace the β?β in both the strings with the appropriate lowercase alphabet, then we only need to calculate the number of steps to convert from A to B.
Say A : βa?pc?β, B : βqfc?dβ
Upon trying brute-force, one can observe that for the above testcase one can conclude that replacing the β?β by βaβ takes only 6 operations.
Number of operations for each index:
- For i = 1, a -> q : 1
- i = 2, a -> f : 1
- i = 3, p -> c : 2
- i = 4, c -> a : 1
- i = 5, a -> d : 1
Hence, the total number of operations becomes 6.
The above approach simply replaces the question mark with each of the lowercase alphabet and checks for which alphabet the number of operations is minimum.
Steps to follow to implement the above approach:
- Initialize two auxiliary strings P and Q.
- Iterate for each alphabet from a β z and replace each instance of β?β in both strings with that alphabet.
- Store the newly formed strings into P and Q.
- Compute the number of operations required to convert P to Q and store it in some cnt variable.
- Update the min_op if the current value of cnt is less than min_op.
- Repeat 3-5 for the next alphabet until z.
Below is the code to implement the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Checking if certain character is // vowel or consonant int isVowel( char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ) return true ; else return false ; } // Function to compute minimum number // of required operations int solve(string A, string B) { // If both strings are already // equal no. of operation required if (A == B) { return 0; } int n = A.size(), minOp = INT_MAX, cnt = 0; // Two auxiliary strings string P = "" , Q = "" ; // Iterate for both the strings // replacing the each occurrence of // '?' with each alphabet (a-z) and // then compute the number // of operations for ( int j = 0; j < 26; j++) { // Re-initialize both P and Q and // operation counter i.e. cnt P = A, Q = B; cnt = 0; // Replace all the occurrences of // '?' in both strings with each // English alphabet iteratively. for ( int i = 0; i < n; i++) { if (P[i] == '?' ) P[i] = char ( 'a' + j); if (Q[i] == '?' ) Q[i] = char ( 'a' + j); } // Calculate the number // of operations required for ( int i = 0; i < n; i++) { // if both characters are // same then no operation // is required if (P[i] == Q[i]) { continue ; } // if both characters are // either vowels or consonants // we need 2 operations as // vowel -> consonant -> vowel else if ((isVowel(P[i]) && isVowel(Q[i])) || (!isVowel(P[i]) && !isVowel(Q[i]))) { cnt += 2; } // if one character is vowel // and other is consonant // then only one conversion // is required else { cnt += 1; } } // Update the variable minOp if // number of operations for // current alphabet is lesser // than existing value minOp = min(minOp, cnt); } // Return final answer return minOp; } // Driver Code int main() { // TestCase 1 string A = "ab?c?" , B = "aeg?k" ; cout << solve(A, B) << endl; // TestCase 2 A = "am??x" , B = "xd?fc" ; cout << solve(A, B) << endl; // TestCase 3 A = "a?pc?" , B = "qfc?d" ; cout << solve(A, B) << endl; return 0; } |
Python3
def isVowel(c): if c = = 'a' or c = = 'e' or c = = 'i' or c = = 'o' or c = = 'u' : return True else : return False def solve(A, B): if A = = B: return 0 n = len (A) minOp = float ( 'inf' ) for j in range ( 26 ): P, Q = A, B cnt = 0 for i in range (n): if P[i] = = '?' : P = P[:i] + chr ( ord ( 'a' ) + j) + P[i + 1 :] if Q[i] = = '?' : Q = Q[:i] + chr ( ord ( 'a' ) + j) + Q[i + 1 :] for i in range (n): if P[i] = = Q[i]: continue elif ((isVowel(P[i]) and isVowel(Q[i])) or ( not isVowel(P[i]) and not isVowel(Q[i]))): cnt + = 2 else : cnt + = 1 minOp = min (minOp, cnt) return minOp # Driver Code if __name__ = = '__main__' : # TestCase 1 A = "ab?c?" B = "aeg?k" print (solve(A, B)) # TestCase 2 A = "am??x" B = "xd?fc" print (solve(A, B)) # TestCase 3 A = "a?pc?" B = "qfc?d" print (solve(A, B)) |
C#
// C# code for the above approach: using System; public class Solution { // Checking if certain character is vowel or consonant public static bool isVowel( char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ) { return true ; } else { return false ; } } // Function to compute minimum number of required // operations public static int solve( string A, string B) { // If both strings are already equal no. of // operation required if (A == B) { return 0; } int n = A.Length, minOp = int .MaxValue, cnt = 0; // Two auxiliary strings string P = "" , Q = "" ; // Iterate for both the strings replacing the each // occurrence of '?' with each alphabet (a-z) and // then compute the number of operations for ( int j = 0; j < 26; j++) { // Re-initialize both P and Q and operation // counter i.e. cnt P = A; Q = B; cnt = 0; // Replace all the occurrences of '?' in both // strings with each English alphabet // iteratively. for ( int i = 0; i < n; i++) { if (P[i] == '?' ) { P = P.Remove(i, 1).Insert( i, char .ConvertFromUtf32( 'a' + j)); } if (Q[i] == '?' ) { Q = Q.Remove(i, 1).Insert( i, char .ConvertFromUtf32( 'a' + j)); } } // Calculate the number of operations required for ( int i = 0; i < n; i++) { // if both characters are same then no // operation is required if (P[i] == Q[i]) { continue ; } // if both characters are either vowels or // consonants we need 2 operations as vowel // -> consonant -> vowel else if ((isVowel(P[i]) && isVowel(Q[i])) || (!isVowel(P[i]) && !isVowel(Q[i]))) { cnt += 2; } // if one character is vowel and other is // consonant then only one conversion is // required else { cnt += 1; } } // Update the variable minOp if number of // operations for current alphabet is lesser // than existing value minOp = Math.Min(minOp, cnt); } // Return final answer return minOp; } // Main function public static void Main() { // TestCase 1 string A = "ab?c?" , B = "aeg?k" ; Console.WriteLine(solve(A, B)); // TestCase 2 A = "am??x" ; B = "xd?fc" ; Console.WriteLine(solve(A, B)); // TestCase 3 A = "a?pc?" ; B = "qfc?d" ; Console.WriteLine(solve(A, B)); } } |
Javascript
// Function to check if a given character is vowel or consonant function isVowel(c) { if (c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u' ) { return true ; } else { return false ; } } // Function to compute minimum number of required operations to convert string A to string B function solve(A, B) { // If both strings are already equal, no operation is required if (A === B) { return 0; } // Initialize variables let n = A.length; let minOp = Infinity; let cnt = 0; let P = '' ; let Q = '' ; // Iterate for each English alphabet from a to z for (let j = 0; j < 26; j++) { // Re-initialize P, Q and cnt for each alphabet P = A; Q = B; cnt = 0; // Replace all the occurrences of '?' in both strings with each English alphabet iteratively for (let i = 0; i < n; i++) { if (P[i] === '?' ) { P = P.substr(0, i) + String.fromCharCode( 'a' .charCodeAt(0) + j) + P.substr(i + 1); } if (Q[i] === '?' ) { Q = Q.substr(0, i) + String.fromCharCode( 'a' .charCodeAt(0) + j) + Q.substr(i + 1); } } // Compute the number of operations required to convert P to Q for (let i = 0; i < n; i++) { if (P[i] === Q[i]) { // If both characters are same then no operation is required continue ; } else if ((isVowel(P[i]) && isVowel(Q[i])) || (!isVowel(P[i]) && !isVowel(Q[i]))) { // If both characters are either vowels or consonants, we need 2 operations as vowel -> consonant -> vowel cnt += 2; } else { // If one character is vowel and other is consonant, then only one conversion is required cnt += 1; } } // Update the variable minOp if number of operations for current alphabet is lesser than existing value minOp = Math.min(minOp, cnt); } // Return final answer return minOp; } // Test Cases let A = 'ab?c?' , B = 'aeg?k' ; console.log(solve(A, B)); A = 'am??x' , B = 'xd?fc' ; console.log(solve(A, B)); A = 'a?pc?' , B = 'qfc?d' ; console.log(solve(A, B)); |
Java
import java.util.*; public class Main { // Checking if certain character is // vowel or consonant public static boolean isVowel( char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ) { return true ; } else { return false ; } } // Function to compute minimum number // of required operations public static int solve(String A, String B) { // If both strings are already // equal no. of operation required if (A.equals(B)) { return 0 ; } int n = A.length(), minOp = Integer.MAX_VALUE, cnt = 0 ; // Two auxiliary strings String P = "" , Q = "" ; // Iterate for both the strings // replacing the each occurrence of // '?' with each alphabet (a-z) and // then compute the number // of operations for ( int j = 0 ; j < 26 ; j++) { // Re-initialize both P and Q and // operation counter i.e. cnt P = A; Q = B; cnt = 0 ; // Replace all the occurrences of // '?' in both strings with each // English alphabet iteratively. for ( int i = 0 ; i < n; i++) { if (P.charAt(i) == '?' ) { P = P.substring( 0 , i) + ( char )( 'a' + j) + P.substring(i+ 1 ); } if (Q.charAt(i) == '?' ) { Q = Q.substring( 0 , i) + ( char )( 'a' + j) + Q.substring(i+ 1 ); } } // Calculate the number // of operations required for ( int i = 0 ; i < n; i++) { // if both characters are // same then no operation // is required if (P.charAt(i) == Q.charAt(i)) { continue ; } // if both characters are // either vowels or consonants // we need 2 operations as // vowel -> consonant -> vowel else if ((isVowel(P.charAt(i)) && isVowel(Q.charAt(i))) || (!isVowel(P.charAt(i)) && !isVowel(Q.charAt(i)))) { cnt += 2 ; } // if one character is vowel // and other is consonant // then only one conversion // is required else { cnt += 1 ; } } // Update the variable minOp if // number of operations for // current alphabet is lesser // than existing value minOp = Math.min(minOp, cnt); } // Return final answer return minOp; } // Driver Code public static void main(String[] args) { // TestCase 1 String A = "ab?c?" , B = "aeg?k" ; System.out.println(solve(A, B)); // TestCase 2 A = "am??x" ; B = "xd?fc" ; System.out.println(solve(A, B)); // TestCase 3 A = "a?pc?" ; B = "qfc?d" ; System.out.println(solve(A, B)); } } |
4 5 6
Time Complexity: O(N*26) ~ O(N)
Auxiliary Space: O(N), auxiliary strings of size N are being used.