Skip to main content
Talentd

Furthest Point From Origin - Solution & Explanation

EasyStringCounting15 min readAsked at: Meta, Barclays, Google +1
Practice this problem

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.

 

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 '_'.

Approach Overview

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.

Approach 1: Approach 1: Maximize L and R Separately

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Simulate Movement with Maximum Flexibility

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Greedy

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), as we are using a fixed amount of additional space.

Approach 2: Simulate Movement with Maximum Flexibility

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.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Maximize L and R SeparatelyO(n)O(1)Clear reasoning approach when explaining both extreme assignments of '_' characters.
Simulate Movement with Maximum FlexibilityO(n)O(1)Preferred solution in interviews; reduces the problem to |R-L| + underscore count.

Video Solution

Furthest Point From Origin | Simple Explanation | Dry Run | Leetcode 2833 | codestorywithMIK • codestorywithMIK • 3,371 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Furthest Point From Origin easy or hard?
Furthest Point From Origin is classified as an Easy problem. The challenge is recognizing that underscore moves can always extend the current displacement, which simplifies the final formula to |R - L| plus the number of underscores.
Furthest Point From Origin Python/Java solution
In both Python and Java, iterate through the string and maintain counters for L, R, and _. After the loop, return Math.abs(R - L) + underscore_count (or abs(R - L) + underscores in Python). The logic is identical across languages and runs in linear time.
How to solve Furthest Point From Origin in O(n)?
Traverse the string and count L, R, and _ characters. Compute the base displacement as R - L. Since each underscore can be assigned to extend movement in the favorable direction, the maximum distance from the origin equals |R - L| + underscores. This requires a single pass over the string.
What is the best approach for Furthest Point From Origin?
The optimal approach counts how many L, R, and _ characters appear in the string. The fixed displacement is R - L, and each underscore can extend the movement in the direction that increases the absolute value. The final answer becomes |R - L| + number_of_underscores. This runs in O(n) time with O(1) extra space.
Is Furthest Point From Origin asked at Google/Amazon/Meta?
This problem reflects a common interview pattern involving greedy reasoning and counting. Variations of flexible-move or maximize-displacement problems appear in interviews at companies like Amazon and Google, especially in early screening rounds focused on string processing and reasoning.
What data structure is used in Furthest Point From Origin?
No complex data structure is needed. The solution uses simple counters while iterating through the string. The key idea comes from counting characters and applying a greedy observation about maximizing absolute displacement.
What is the time complexity of Furthest Point From Origin?
The solution runs in O(n) time because the string is scanned once to count moves. Space complexity is O(1) since only a few integer counters are stored. No additional data structures are required.

Ready to solve this problem?

Practice Furthest Point From Origin with our built-in code editor and test cases.

Practice on FleetCode
Previous

Robot Return to Origin