## PROBLEM LINK

## Contributors

**Author:** Amit Pandey

**Tester & Editorialist:** Prateek Gupta

## DIFFICULTY:

Simple

## PREREQUISITES:

None

## PROBLEM:

Given two strings X and Y of length N, form another string Z of same length such that the hamming distance(X, Z) + hamming distance(Y, Z) is maximized. If there are many such types of Z possible, print the lexicographically smallest one.

## EXPLANATION

**Solution for Subtask 1:**

This subtask can indeed be solved by Bit Masking. We can generate all possible strings where each character will be either ‘W’ or ‘B’. For each such string, we can track the maximum sum of hamming distances and the corresponding string which gave us the new maximum. In case, we have the same maximum, it is fine to compare the string and store the one which is lexicographically smaller. Lets look at the pseudo code to understand how this works.

```
F(N, X, Y) {
string Z;
int max_val = -1
for mask in range(0, 2^N) {
string tmp = ""
int hamming_sum = 0
for i in range(0, N) {
if ( bit i is set in mask ) tmp.append('W')
else tmp.append('B')
hamming_sum += (tmp[i] != X[i]) + (tmp[i] != Y[i])
if ( hamming_sum > max_val )
max_val = hamming_sum, Z = tmp
else if ( hamming_sum == max_val )
Z = min(Z, tmp)
}
}
return Z
}
```

**Solution for subtask 2 & 3:**

In order to maximize the sum of hamming distance between string (X, Z) and string (Y, Z), we can greedily decide to fill each position of Z with either ‘B’ or ‘W’. At each position, there are only two possible cases for us to consider.

- If $X_{pos}$ and $Y_{pos}$ are same, the best decision will be to insert the character which is not equal to $X_{pos}$ or $Y_{pos}$ since it will fetch you a value of +2 to your sum of hamming distances.
- If $X_{pos}$ is not equal to $Y_{pos}$, then you can insert any character since it will fetch you a value of +1. But, you also need to make your string $Z$ lexicographically smaller. Hence, you should insert character 'B' since 'B' < 'W' in terms of lexicographical nature.

Fore more details on the implementation of any of the subtasks, have a look at the tester’s solution.

## COMPLEXITY

As the string Z can just be found in a single traversal, the overall time complexity of the solution is \mathcal{O}(N).

## SOLUTIONS

Setter

Tester’s solution to Subtask 1

Tester’s solution to Subtask 2