Fails for simple test case:

4

abab

baba

Answer = 1. Your output = 2

Also I think its a DP problem

For the first problem I think that the following greedy algorithm does the job but I am not sure. Please, correct me if I am wrong! :)

Loop over the positions and let's say that the current position is i (1 <= i <= N). If A[i]=B[i], then we can't change anything. Assume that A[i]!=B[i]. If there are no restrictions for both A[i] and B[i] (restriction means that it is said that A[i] or B[i] should be in the first or in the second string), then let's say that A[i] should be in the first string and B[i] should be in the second string. If there is a restriction for one of them make that the restriction is fulfilled (swap them if it is needed) and say that the other character (A[i] or B[i]) should be in its new positions. If there is a restriction for both of them, then try not to break it (it is possible only if the restrictions for A[i] and B[i] is for different strings). If it is impossible not to break the restriction, then try not to insert a new character in any string. Let's say that both A[i] and B[i] should be in the first string. If the character A[i] appears in the second string, the swap A[i] and B[i]. Otherwise, don't swap them

For example, let's take the strings "dir" and "rid".

For the first position there is no restriction for 'd' or 'r'. So let's say that 'd' should be in the first string and 'r' should be in the second string. Let's move to the second position. There are two equal characters so we can't change anything and skip it. Let's move to the third position. We should swap A[3] and B[3] since there is a restriction for both 'r' and 'd'. Now, we produced the strings "did" and "rir", so the answer should be 2.

No one talked about Q2 probably because it's simpler: for each iteration of i, try to determine the difference between number of comparisons and swaps you will do for that iteration. It's one of two possible values; now you only need to figure out when it's one and when it's the other.

Q1 looks more complicated, though. I don't know if there's anything simple I'm missing. Were there any constraints on the input strings A and B?

Second question is relatively easy. It can be solved binary indexed tree , binary search but both will be overkill. As we need to count the difference of comparison and swaps. Comparisons will be one more than the swaps if the number is not the current smallest otherwise it is equal.

Int calculate(int a[],int n){ Curr = inf ; Int ans = n ; For(int I=0;I<=n;I++){ If(curr > a[I]) ans --; Curr = min(curr,a[I]) ; Return ans ; }

If n is small (30-50) , we can also brute force through all the permutations in O(2^n).

Edit : my bad