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:
moves[i] = 'L' or moves[i] = '_'moves[i] = 'R' or moves[i] = '_'Return the distance from the origin of the furthest point you can get to after n moves.
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 <= 50moves consists only of characters 'L', 'R' and '_'.Problem Overview: You start at position 0 on a number line and execute a sequence of moves represented by a string. L moves left, R moves right, and _ can be either. The goal is to assign each underscore optimally so the final position is as far from the origin as possible.
Approach 1: Maximize L and R Separately (O(n) time, O(1) space)
Scan the string once and count how many L, R, and _ characters appear. The final position after fixed moves is R - L. Each underscore can be converted to either direction, so the trick is to push the position further from zero. You compute two possibilities: treat all underscores as R or treat all underscores as L. That gives distances |(R + _) - L| and |R - (L + _)|. The maximum of these two values is the furthest point reachable. This works because every underscore contributes exactly one step and the optimal strategy is to move consistently in the direction that increases absolute displacement.
Approach 2: Simulate Movement with Maximum Flexibility (O(n) time, O(1) space)
Instead of evaluating two scenarios explicitly, track the current displacement while scanning the string. Increase a counter for R, decrease it for L, and count underscores separately. After processing the entire string, the fixed displacement is pos and you have blank flexible moves. The maximum possible distance from the origin becomes |pos| + blank. Each underscore can always extend the current direction of movement, so they simply add to the absolute displacement. This approach expresses the same idea as the previous one but with fewer intermediate calculations.
Both approaches rely on simple string traversal and basic counting. No extra data structures are needed because the order of operations does not affect the final displacement—only the counts of each move type matter.
Recommended for interviews: The counting-based formula from Approach 2 is what interviewers typically expect. It shows you recognized that underscores are flexible moves and that maximizing the absolute displacement reduces to |R - L| + _. Explaining Approach 1 first can demonstrate reasoning about edge cases, but the simplified formula proves you spotted the core pattern quickly.
In this approach, you need to count the maximum distance from the origin both in the negative and positive directions independently. For each 'L', decrease the position, for each 'R', increase the position and for '_', consider both possibilities of increment or decrement. Finally, take the maximum of the absolute values of these two calculated distances.
This Python function uses the count method to calculate the potential maximum steps in both the left and right directions. The total steps towards the left (negative direction) can be the sum of 'L' and '_', while the total steps towards the right (positive direction) can be the sum of 'R' and '_'. The answer will be the maximum of these two values.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, as we are iterating over the string a few times.
Space Complexity: O(1), as we are using a fixed amount of additional space.
This approach uses a simulation strategy, keeping track of two possibilities: one favoring maximum left movement and the other favoring maximum right movement from the start. By iterating once, adjust both positions based on the character read, choosing left or right for the underscore as needed.
The above Python implementation mimics potential movement paths by simulating two cores: one prioritizing left steps for `_` initially, and the other prioritizing right steps. At each underscore, the left pathway decreases and the right pathway increases, allowing flexibility to achieve the maximum distance in the end calculation.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), as it loops once through the string.
Space Complexity: O(1), as no additional structures with a size dependency on input length are used.
When encountering the character '', we can choose to move left or right. The problem requires us to find the farthest point from the origin. Therefore, we can first traverse once, greedily move all '' to the left, and find the farthest point from the origin at this time. Then traverse again, greedily move all '_' to the right, and find the farthest point from the origin at this time. Finally, take the maximum of the two traversals.
Further, we only need to calculate the difference between the number of 'L' and 'R' in the string, and then add the number of '_'.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Maximize L and R Separately | Time Complexity: O(n), where n is the length of the string, as we are iterating over the string a few times. |
| Approach 2: Simulate Movement with Maximum Flexibility | Time Complexity: O(n), as it loops once through the string. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Maximize L and R Separately | O(n) | O(1) | Clear reasoning approach when explaining both extreme assignments of '_' characters. |
| Simulate Movement with Maximum Flexibility | O(n) | O(1) | Preferred solution in interviews; reduces the problem to |R-L| + underscore count. |
Leetcode Weekly contest 360 - Easy - Furthest Point From Origin • Prakhar Agrawal • 1,197 views views
Watch 9 more video solutions →Practice Furthest Point From Origin with our built-in code editor and test cases.
Practice on FleetCode