Furthest Point From Origin

Problem Description

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.

Key Insights

• Each 'L' move decreases the position by 1.
• Each 'R' move increases the position by 1.
• Each '_' can be used as either 'L' or 'R', effectively giving you flexibility in maximizing your distance.
• The furthest point can be calculated by determining the net moves available and maximizing the distance in either direction using the underscores.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can iterate through the moves string and count the number of 'L', 'R', and '_' characters. The furthest distance from the origin can be calculated as follows:

1. Count the number of left moves (L) and right moves (R).
2. Count the number of underscores (_).
3. The furthest distance can be calculated as the absolute value of the difference between the left moves and right moves, plus the total number of underscores. This gives us the maximum flexibility to either direction.

Code Solutions