2833. Furthest Point From Origin

Problem statement

You are given a string moves of length n consisting only of characters 'L', 'R', and '_'. The string represents your movement on a number line starting from the origin 0.

In the ith move, you can choose one of the following directions:

• Move to the left if moves[i] = 'L' or moves[i] = '_'
• Move to the right if moves[i] = 'R' or moves[i] = '_'

Return the distance from the origin of the furthest point you can get to after n moves.

Examples

Example 1

Input: moves = "L_RL__R"
Output: 3

Explanation: The furthest point we can reach from the origin 0 is point -3 through the following sequence of moves "LLRLLLR".

Example 2

Input: moves = "_R__LL_"
Output: 5

Explanation: The furthest point we can reach from the origin 0 is point -5 through the following sequence of moves "LRLLLLL".

Example 3

Input: moves = "_______"
Output: 7

Explanation: The furthest point we can reach from the origin 0 is point 7 through the following sequence of moves "RRRRRRR".

Constraints

• 1 <= moves.length == n <= 50
• moves consists only of characters 'L', 'R', and '_'

Explanation

The string contains three kinds of characters:

• 'L' — forces a left move
• 'R' — forces a right move
• '_' — can be chosen as either left or right

Our goal is to end up as far from the origin as possible. That means we should make all our moves in the same direction, either all left or all right, because any left-right pair cancels out.

Since 'L' and 'R' are fixed, the only freedom we have is deciding the direction of each '_'. The optimal strategy is to replace every '_' with whichever of 'L' or 'R' already appears more often. That maximizes the net displacement.

To see why this works, think in terms of cancellation:

• Every 'L' contributes -1 to the position
• Every 'R' contributes +1 to the position
• If we have countL left moves and countR right moves, the min(countL, countR) pairs cancel each other out

After cancellation, the remaining fixed moves contribute |countL - countR| to the distance. Each '_' adds one more unit in whichever direction we choose. So the total maximum distance is:

|countL - countR| + count_ = moves.size() - 2 * min(countL, countR)

This single formula captures the whole idea.

Code

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int countL = count(moves.begin(), moves.end(), 'L');
        int countR = count(moves.begin(), moves.end(), 'R');
        return moves.size() - 2 * min(countL, countR);
    }
};