Minimum operations to make strings equal
You have been given two strings A and B consisting of lower case English letters. The task is to count the minimum number of pre-processing moves on the string A required to make it equal to string B after applying below operations:

1. Choose any index i (0

Question

Minimum operations to make strings equal

You have been given two strings A and B consisting of lower case English letters. The task is to count the minimum number of pre-processing moves on the string A required to make it equal to string B after applying below operations:

1. Choose any index i (0 <= i < n) and swap characters a[i]  and b[i].
2. Choose any index i (0 <= i < n) and swap characters a[i]  and a[n-i-1] .
3. Choose any index i (0 <= i < n) and swap characters b[i]  and b[n-i-1] .

In one preprocess move, you can replace a character in A with any other character of the English alphabet.

Note:

1. The number of changes you make after the preprocess move does not matter.
2. You cannot apply to preprocess moves to the String B or make any preprocess moves after the first change is made.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains string A consisting of lowercase English letters.

The second line of each test case contains string B consisting of lowercase English letters.

Output Format:

For each test case, print a single integer denoting the minimum number of pre-processing moves on the string A required to make it equal to the string B. Print -1, if it is impossible to make strings equal.

The output for each test case is in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given fuction.

Constraints:

1 <= T <= 100
1 <= N <= 5000

Where ‘N’ is the length of the strings.

Time Limit: 1 sec

Accepted Answer

Using Variables

Let’s divide all characters of both strings into groups in such a way that characters in each group can be swapped with each other with changes. So, there will be the following groups: {'A'[0], ‘A’['N'-1], ‘B’[0], ‘B’['N'-1]}, {'A'[1], ‘A’['N'-2], ‘B’[1], ‘B’['N'-2]} and so on. Since these groups don’t affect each other, we can calculate the number of pre-processing moves in each group and then sum it up.

Now, for each group of letters ‘A’[i], ‘A’['N' - i - 1], ‘B’[i] and ‘B’['N' - i - 1] (further denoted as ‘C1’, ‘C2’, ‘C3’ and ‘C4’ respectively), we have all these possible cases:

The group that doesn’t require any preprocessing move, if:
- All four characters are same, i.e. ‘C1’ == ‘C2’ == ‘C3’ == ‘C4’ or,
- Pairwise equal characters, i.e.
  - ‘C1’ == ‘C2’ && ‘C3’ == ‘C4’
  - ‘C1’ == ‘C3’ && ‘C2’ == ‘C4’
  - ‘C1’ == ‘C4’ && ‘C2’ == ‘C3’
The group that requires only one preprocessing move, if:
- ‘C1’ == ‘C3’
- ‘C1’ == ‘C4’
- 'C2' == 'C3'
- ‘C2’ == ‘C4’
- ‘C3’ == ‘C4’
All the remaining cases require two preprocessing moves.

For every group of letters, we analyze according to the above cases. The strings with odd numbers of letters represent one edge case. Therefore, the letter in the middle must be taken into account separately, i.e. if the characters in this group are equal, the answer is ‘0’; otherwise, it’s '1', because we have to change it.

Space Complexity: O(1)Explanation:

O(1)

Since no extra memory is used except for some variables, thus, the space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the given strings.

Since we are traversing the string only once, thus, the time complexity will be O(N).

Accepted Answer

Using HashMap

Let’s divide all characters of both strings into groups in such a way that characters in each group can be swapped with each other with changes. So, there will be the following groups: {'A'[0], ‘A’['N'-1], ‘B’[0], ‘B’['N'-1]}, {'A'[1], ‘A’['N'-2], ‘B’[1], ‘B’['N'-2]} and so on... Since these groups don’t affect each other, we can calculate the number of pre-processing moves in each group and then sum it up.

How to determine if a group does not need any pre-processing moves?

For a group consisting of ‘2’ characters (there will be one such group if ‘N’ is odd), that’s easy - If the characters in this group are equal, the answer is ‘0’; otherwise, it’s ‘1’.

To determine the required number of pre-processing moves for a group consisting of four characters, we may use the following fact: this group doesn’t require any pre-processing moves if the characters in this group can be divided into pairs. So if the group contains four equal characters or two pairs of equal characters, then the answer for this group is 0. Otherwise, we may check that replacing only one character of ‘A’[i] and ‘A’['N' - 'i' - 1] will be enough. If so, then the answer is ‘1’; otherwise, it’s ‘2’.

We will use HashMap to count the number of distinct characters in a particular group. The key in the HashMap will be the character itself, and the value corresponding to that key will be its frequency.

Space Complexity: O(1)Explanation:

O(1), i.e. constant space complexity.

Since no extra memory is used except a HashMap of size 4, which is constant with respect to the length of the string, so, overall space complexity will be constant.

Time Complexity: O(1)Explanation:

O(N), where ‘N’ is the length of the given strings.

Since we are traversing in the given string only once, also, insertion and searching operations take constant time into the HashMap. So, overall time complexity will be O(N).

Accepted Answer

10

Accepted Answer

Choose any index i (0 <= i < n) and swap characters a[i] and b[i]. 2. Choose any index i (0 <= i < n) and swap characters a[i] and a[n-i-1] . 3. Choose any index i (0 <= i < n) and swap characters b[i] and b[n-i-1] .

Accepted Answer

Using Variables

Let’s divide all characters of both strings into groups in such a way that characters in each group can be swapped with each other with changes. So, there will be the following groups: {'A'[0], ‘A’['N'-1], ‘B’[0], ‘B’['N'-1]}, {'A'[1], ‘A’['N'-2], ‘B’[1], ‘B’['N'-2]} and so on. Since these groups don’t affect each other, we can calculate the number of pre-processing moves in each group and then sum it up.

Now, for each group of letters ‘A’[i], ‘A’['N' - i - 1], ‘B’[i] and ‘B’['N' - i - 1] (further denoted as ‘C1’, ‘C2’, ‘C3’ and ‘C4’ respectively), we have all these possible cases:

The group that doesn’t require any preprocessing move, if:

All four characters are same, i.e. ‘C1’ == ‘C2’ == ‘C3’ == ‘C4’ or,

Pairwise equal characters, i.e.

‘C1’ == ‘C2’ && ‘C3’ == ‘C4’

‘C1’ == ‘C3’ && ‘C2’ == ‘C4’

‘C1’ == ‘C4’ && ‘C2’ == ‘C3’

The group that requires only one preprocessing move, if:

‘C1’ == ‘C3’

‘C1’ == ‘C4’

'C2' == 'C3'

‘C2’ == ‘C4’

‘C3’ == ‘C4’

All the remaining cases require two preprocessing moves.

For every group of letters, we analyze according to the above cases. The strings with odd numbers of letters represent one edge case. Therefore, the letter in the middle must be taken into account separately, i.e. if the characters in this group are equal, the answer is ‘0’; otherwise, it’s '1', because we have to change it.

Space Complexity: O(1)Explanation:

O(1)

Since no extra memory is used except for some variables, thus, the space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the given strings.

Since we are traversing the string only once, thus, the time complexity will be O(N).

You have been given two strings A and B consisting of lower case English letters. The task is to count the minimum number of pre-processing moves on the string A required to make it equal to string B after applying below operations:

In one preprocess move, you can replace a character in A with any other character of the English alphabet.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Wipro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Wipro Software Developer