Intuition
As we can increment as well as decrement any character, we can simply change any character to any other character in two ways, one is by consistently increasing until we reach that character, and the other is consistently decreasing until we reach that character. So following this intuition, we can always choose the minimum operation out of the two ways to convert a character to any other desired character.
Also see, Euclid GCD Algorithm
Algorithm:
- Function countOperations() will be used to count the number of minimum operations to convert characters of ‘STR1’ to characters present in ‘STR2’.
- To account for the characters present in the string ‘STR2’, we can use a boolean array ‘isPresent’ of size equal to the number of lowercase alphabet characters, i.e., 26.
- In function countOperations(), we can iterate through each character ‘c’ of ‘STR1’ and find the minimum number of moves to convert it to any character present in string ‘STR2’.
- Finally, add the operations to the variable ‘count’ and return
The implementation of the above algorithm can be understood by the below program.
Program
// Program to find minimum operations to convert characters of STR1 to STR2.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Function to find minimum operations to convert characters of STR1 to STR2.
int countOperations(string STR1, string STR2)
{
// Vector to account the characters of string STR2.
vector<bool> isPresent(26, false);
for (int i = 0; i < STR2.length(); i++)
isPresent[STR2[i] - 'a'] = true;
// Variable to store the count of operations.
int count = 0;
// Traversing through the string STR1 to find operations to convert its characters.
for (int i = 0; i < STR1.length(); i++)
{
// Variable to store minimum moves and current character index, respectively.
int tmp = INT_MAX, idx = STR1[i] - 'a';
// Trying for every lowercase character to obtain minimum moves.
for (int j = 0; j < 26; j++)
{
// If no character corresponding to current 'j' is not present in STR2.
if (!isPresent[j])
continue;
//Direct difference, incrementing and decrementing.
tmp = min(min(abs(j - idx), min(26 - idx + j, idx + 26 - j)), tmp);
}
// Updating the count of operations.
count += tmp;
}
// Returning the final count.
return count;
}
// Main Function.
int main()
{
// Input for string STR1 and STR2.
string STR1, STR2;
cin >> STR1 >> STR2;
// Final answer.
int ans = countOperations(STR1, STR2);
cout << ans;
}
You can also try this code with Online C++ Compiler
Example
Input
abzwe
def
Output
16
Complexity Analysis
Time Complexity: O(max(N, M)), where ‘N’ is the size of ‘STR1’ and ‘M’ is the size of ‘STR2’.
Explanation: We are traversing through ‘STR2’ and ‘STR1’, so the greater size between them will decide the time complexity.
Auxiliary Space: O(1)
Explanation: Only a boolean vector to store 26 bools is used, which is considered to be constant space, thus O(1).
Key Takeaways
The above blog has covered an important interview question frequently asked in big MNCs where Data Structures and Algorithms play an important role. Lexicographically incrementing or decrementing characters to convert characters of string1 to characters present in string2 is a good problem to cover concepts like lexicographical order and string.
Recommended problems -
Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!
34+ registered 
