Lexicographically Incrementing or Decrementing Characters to Convert Characters of STRING1 to Characters Present in STRING2

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;
}

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 the Shortest Substring in a String
• Subsequence of a String
• Beautiful String

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!