Maximum point to convert string S to T by swapping adjacent characters – GeeksforGeeks

Given two strings S and T of length N, the task is to find the maximum points gained in converting the string S into string T by performing the following operation on string S:

• In one move, select an index i (1 ≤ i ≤ N−1), get (S_i − S_{i + 1}) points, and then swap S_i and S_{i + 1}

Examples:

Input: S = “321”, T = “123”
Output: 4

Explanation: One possible sequence of moves is the following:
Select i = 1. Total points = 1, and S will become “312”.
Select i = 0. Total points = 1 + 2, and S will become “132”.
Select i = 1. Total points = 1 + 2 + 1 = 4, and S will become “123”.
Hence total 4 point gained to convert a string S into string T.

Input: S = “12”, T = “21”

Output: -1
Explanation: Only one operation is possible i.e., select i = 0 and swap S[0] and S[1].

Approach: The problem can be solved based on the following observation:

Observations:

Suppose we do a number of swaps to S to make it equal to T, and the element at index i in the original array is now at index pos_i. Let’s find the total cost incurred in the above case:

• Every time we swap element S_i(of the original string) with the character S_j to its right:
  • pos_i increases by 1, pos_j decreases by 1, the cost increases by S_i−S_j.
• We can therefore notice that every time pos_i is increased by 1, the cost increases by S_i. Similarly, the cost decreases by S_i every time pos_i is decreased by 1.
• In the end, the total number of times the cost increases by S_i is equal to pos_i − i (the cost decreases if pos_i − i is negative).

Therefore, we can calculate the cost contributed by each S_i separately and then add them together, giving us the equation ∑S_i(pos_i−i). See, S_i * pos_i can be interpreted as T_j * j.

• When the elements of S are distinct, array pos is unique and the total cost is therefore fixed. 
• When the elements of S are repeated, then any sequence of swaps that makes S equal T has the same total cost
• Therefore, given S and T, it suffices to find any valid mapping pos such that T_posi = S_i. We can then use the equation given above to calculate the answer.

Follow the steps mentioned below to implement the above idea:

• Calculate the sum of all characters in S multiplied by their index.
• Calculate the sum of all characters in T multiplied by their index.
• Subtract the sum of S from the sum of T and print the result.

Below is the implementation of the above approach.

Time Complexity: O(N) 
Auxiliary Space: O(1)