1.
Introduction
2.
Problem Statement
2.1.
Example:
3.
Intuition
4.
Algorithm:
5.
Program
5.1.
Example
6.
Complexity Analysis
7.
Key Takeaways
Last Updated: Mar 27, 2024

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

## Introduction

In a product-based company, we are problems related to the basic data structures like arrays, strings, etc. Let’s learn about some concepts related to strings in this blog.

The string is a fundamental data structure used to store the sequence of characters. Problems related to strings are beneficial in building the foundation of a good programmer. Below is a problem related to strings, which will eventually teach us some concepts about string manipulation.

One more term, which is important to be aware of while solving string-related problems, is Lexicographical order. Lexicographical order is nothing but the dictionary order or preferably the order in which words appear in the dictionary.

## Problem Statement

Two strings, consisting of lowercase alphabet characters, ‘STR1’ and ‘STR2’, are given. We have to find the minimum number of operations to be applied on ‘STR1’ so that it contains only the characters present in the string ‘STR2’. In one operation, we can either:

• Change the current character to the next lexicographical character, or
• Change the current character to the previous lexicographical character

Note: The next character for ‘z’ will be ‘a’, and the previous character for ‘a’ will be ‘z’.

### Example:

Input: STR1 = “abce”, STR2 = “abc”

Output: 2

Explanation: The only character in ‘STR1’, not present in ‘STR2’, is ‘e’. So we can change it to ‘c’ with the second operation two times. The final ‘STR1’ will be “abcc”.

Input: STR1 = “zeh’, STR2 = “ahg”

Output: 3

Explanation: The characters at index 0 and 1 need to be changed as ‘z,’ and ‘e’ is not present in ‘STR2’. So changing ‘z’ to ‘a’ will take one operation, and ‘e’ to ‘g’ takes two operations. So total 3 operations and the final string ‘STR1’ will be “agh”.

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

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 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!

Live masterclass