Problem Statement:

Some robots are standing on an infinite number line with their initial coordinates given by a 0-indexed integer array nums and will start moving once given the command to move. The robots will move a unit distance each second.

You are given a string s denoting the direction in which robots will move on command. 'L' means the robot will move towards the left side or negative side of the number line, whereas 'R' means the robot will move towards the right side or positive side of the number line.

If two robots collide, they will start moving in opposite directions.

Return the sum of distances between all the pairs of robots d seconds after the command. Since the sum can be very large, return it modulo 10⁹ + 7.

Note:

For two robots at the index i and j, pair (i,j) and pair (j,i) are considered the same pair.
When robots collide, they instantly change their directions without wasting any time.
Collision happens when two robots share the same place in a moment.
- For example, if a robot is positioned in 0 going to the right and another is positioned in 2 going to the left, the next second they'll be both in 1 and they will change direction and the next second the first one will be in 0, heading left, and another will be in 2, heading right.
- For example, if a robot is positioned in 0 going to the right and another is positioned in 1 going to the left, the next second the first one will be in 0, heading left, and another will be in 1, heading right.

Example 1:

Input: nums = [-2,0,2], s = "RLL", d = 3
Output: 8
Explanation: 
After 1 second, the positions are [-1,-1,1]. Now, the robot at index 0 will move left, and the robot at index 1 will move right.
After 2 seconds, the positions are [-2,0,0]. Now, the robot at index 1 will move left, and the robot at index 2 will move right.
After 3 seconds, the positions are [-3,-1,1].
The distance between the robot at index 0 and 1 is abs(-3 - (-1)) = 2.
The distance between the robot at index 0 and 2 is abs(-3 - 1) = 4.
The distance between the robot at index 1 and 2 is abs(-1 - 1) = 2.
The sum of the pairs of all distances = 2 + 4 + 2 = 8.

Example 2:

Input: nums = [1,0], s = "RL", d = 2
Output: 5
Explanation: 
After 1 second, the positions are [2,-1].
After 2 seconds, the positions are [3,-2].
The distance between the two robots is abs(-2 - 3) = 5.

Constraints:

2 <= nums.length <= 10⁵
-2 * 10⁹ <= nums[i] <= 2 * 10⁹
0 <= d <= 10⁹
nums.length == s.length
s consists of 'L' and 'R' only
nums[i] will be unique.

Solution:

This problem has a trick. I could not do it during contest but later realized the trick.

The fact that the robots change directions at collision means nothing. We can just consider they switched IDs because at the end we really only care about the positions of the robots as a whole. We do not really care about where robot number so and so is. What this means is that we can solve the problem as if each robot is on its own track and the solution will still work. Here is an example. Consider the problem: nums = [-2,0,2], s = "RLL", d = 3. Then, with the robots changing directions, we have at the end [-3,-1,1] and without changing directions we will have [1,-3,-1]. Realize that both of these will give the same answer.
The second problem is how to calculate the sum of absolute differences in $O(n)$ time. We can sort the final array and then use a heuristic to find answer. Consider the final positions sorted array is [a,b,c,d,e]. Then we need to do (4-0)e + (3-1)d + (2-2)c + (1-3)b + (0-4)a. This is essentially nums[i] * (i - (n-1-i)) which we can sum for all i to get the answer.
The third and final trick is that int does not work because of overflow issues. Use long long and even then you will need to apply mod at each step to get AC.

 
int sumDistance(vector<int>& nums, string s, int d) 
{
    int n=nums.size(), mod=1e9+7;;
    long long res = 0;
    unordered_map<char,int> dirs { {'L',-1}, {'R',1} };
    for (int i=0; i<n; i++) nums[i] += dirs[s[i]] * d;
    sort(nums.begin(),nums.end());
    for(int i=0; i<n; i++) 
    {
        res += (long long)nums[i] * (2*i+1-n);
        res %= mod;
    }
    return res;
}

TC: $O(n\log(n))$ because sorting is involved.