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 '_'.In #2833 Furthest Point From Origin, you start at position 0 and follow a sequence of moves represented by a string. Each character moves you left (L), right (R), or acts as a flexible move (_) that can be chosen as either direction. The goal is to determine the maximum possible distance from the origin after all moves.
A useful observation is that only the difference between left and right moves determines the final displacement. You can iterate through the string and count occurrences of L, R, and _. The flexible moves can then be assigned strategically to push the final position farther from zero.
By treating _ characters as adjustable moves, you maximize the magnitude of the final displacement based on the existing imbalance between L and R. This leads to a simple single-pass counting approach with O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single-pass counting of L, R, and _ | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
<div class="_1l1MA">In an optimal answer, all occurrences of <code>'_’</code> will be replaced with the <strong>same</strong> character.</div>
<div class="_1l1MA">Replace all characters of <code>'_’</code> with the character that occurs the most. </div>
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in coding interviews, especially for entry-level roles. It tests basic string processing, counting techniques, and the ability to reason about maximizing outcomes.
The optimal approach is a counting strategy. Iterate through the string and count how many 'L', 'R', and '_' characters appear. The '_' characters can be assigned in the direction that maximizes the final distance from the origin.
The '_' characters act as flexible moves that can be interpreted as either 'L' or 'R'. By assigning them strategically, you can increase the overall displacement and maximize the distance from the origin.
No complex data structure is required. Simple integer counters for 'L', 'R', and '_' are sufficient, making the solution efficient and easy to implement.