LeetCode 2833 - Furthest Point From Origin

LeetCode Problem 2833

Difficulty: 🟢 Easy
Topics: String, Counting

Solution

Problem Understanding

This problem asks us to determine the maximum possible distance from the origin after performing a sequence of moves on a number line.

We start at position 0, and we are given a string moves, where each character represents one movement instruction. Each move can shift the current position either left (-1) or right (+1).

The movement rules are:

• 'L' means we must move left.
• 'R' means we must move right.
• '_' means we may choose either left or right.

The key detail is that underscore ('_') characters are flexible. We are allowed to decide their direction in a way that maximizes the final distance from the origin. The result should be the absolute distance from 0, not necessarily the position itself. That means ending at +5 and -5 are equally good because both are distance 5 from the origin.

Restating the problem in simpler terms, we want to make the best choices for every '_' so that the final position is as far from zero as possible.

For example, if we already have more left moves than right moves, then assigning all underscores as additional left moves pushes us even farther from the origin. Similarly, if right moves dominate, we should assign underscores to the right.

The constraints tell us that:

• 1 <= moves.length <= 50
• The string contains only 'L', 'R', and '_'.

Since the input size is extremely small, even inefficient solutions would work. However, the problem has a very simple mathematical observation that allows an optimal linear-time solution.

There are several important edge cases worth considering upfront.

If the string contains only underscores, such as "_______", then we can choose the same direction every time, producing the maximum possible distance equal to the string length.

If left and right moves are balanced, such as "LRLR__", the fixed moves cancel each other out. In this case, all underscores should be assigned in the same direction to maximize distance.

If there are no underscores at all, the answer is simply the absolute difference between the number of left and right moves.

The problem guarantees valid input, so we do not need to handle invalid characters or empty strings.

Approaches

Brute Force Approach

A brute-force solution would try every possible assignment of underscores.

Suppose there are k underscore characters. Each underscore has two possible choices:

• Replace with 'L'
• Replace with 'R'

That means there are 2^k possible combinations. For each combination, we could simulate the movement and compute the final distance from the origin, then take the maximum.

This approach is correct because it explicitly checks every possible valid sequence of moves. Since it explores all outcomes, it cannot miss the optimal answer.

However, this method becomes inefficient when the number of underscores grows. In the worst case, if the string length is 50 and all characters are underscores, we would need to examine 2^50 possibilities, which is computationally infeasible.

Optimal Approach

The key observation is that only the final distance matters.

Let:

• L = number of left moves
• R = number of right moves
• _ = number of flexible moves

Without underscores, the position would be:

$$R - L$$

Each underscore can either add +1 or -1.

To maximize distance from zero, all underscores should be assigned in the direction that pushes us farther away from the origin.

If left moves dominate, we assign every underscore to the left.

If right moves dominate, we assign every underscore to the right.

If they are equal, we may choose either side.

This means the answer becomes:

$$|R - L| + _$$

The intuition is simple: the fixed imbalance between left and right gives us a starting advantage, and every underscore can increase that advantage by exactly 1.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^k × n)	O(1)	Tries every underscore assignment
Optimal	O(n)	O(1)	Counts characters and uses a mathematical observation

Algorithm Walkthrough

1. Initialize counters for left moves, right moves, and flexible moves.

We need to know how many 'L', 'R', and '_' characters exist because the final answer depends only on their counts. 2. Traverse the string once.

For each character:

• If it is 'L', increment the left counter.
• If it is 'R', increment the right counter.
• Otherwise, increment the underscore counter.

This single pass gives us complete information about the movement possibilities. 3. Compute the fixed displacement.

The guaranteed movement contribution is:

$$|R - L|$$

This represents how far we would already be from the origin without considering underscores. 4. Add all underscore moves.

Since every underscore can be chosen to reinforce the dominant direction, each one increases the distance by exactly 1.

Therefore:

$$\text{answer} = |R - L| + _$$ 5. Return the result.

Why it works

The algorithm works because the only thing that matters is the final displacement. Any underscore move can either increase or decrease the current imbalance between left and right. To maximize the final absolute distance, every underscore should reinforce the larger side. Since each underscore changes displacement by exactly 1, the optimal strategy is always to add all underscores to the existing imbalance, producing:

$$|R - L| + _$$

This guarantees the maximum possible distance.

Python Solution

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        left_count = 0
        right_count = 0
        flexible_count = 0

        for move in moves:
            if move == 'L':
                left_count += 1
            elif move == 'R':
                right_count += 1
            else:
                flexible_count += 1

        return abs(right_count - left_count) + flexible_count

The implementation follows the algorithm directly.

We first initialize three counters to track the number of left, right, and flexible moves. Then we iterate through the string exactly once and update the appropriate counter based on the current character.

After counting is complete, we calculate the absolute difference between right and left moves. This gives the unavoidable displacement caused by fixed instructions. Finally, we add the number of underscores because every flexible move can be chosen to extend the displacement in the favorable direction.

The solution is concise because the problem reduces to a counting exercise rather than an actual movement simulation.

Go Solution

func furthestDistanceFromOrigin(moves string) int {
	leftCount := 0
	rightCount := 0
	flexibleCount := 0

	for _, move := range moves {
		if move == 'L' {
			leftCount++
		} else if move == 'R' {
			rightCount++
		} else {
			flexibleCount++
		}
	}

	difference := rightCount - leftCount
	if difference < 0 {
		difference = -difference
	}

	return difference + flexibleCount
}

The Go implementation follows the same logic as the Python version. Since Go does not have a built-in abs() function for integers in the standard library, we manually compute the absolute difference by checking whether the value is negative.

There are no concerns about integer overflow because the maximum string length is only 50, making the result very small. Since strings in Go are iterable using range, we can process each character efficiently without converting the string into a slice.

Worked Examples

Example 1

Input: moves = "L_RL__R"

Step	Character	Left Count	Right Count	Flexible Count
1	L	1	0	0
2	_	1	0	1
3	R	1	1	1
4	L	2	1	1
5	_	2	1	2
6	_	2	1	3
7	R	2	2	3

Final calculation:

$$|2 - 2| + 3 = 3$$

Output: 3

Example 2

Input: moves = "_R__LL_"

Step	Character	Left Count	Right Count	Flexible Count
1	_	0	0	1
2	R	0	1	1
3	_	0	1	2
4	_	0	1	3
5	L	1	1	3
6	L	2	1	3
7	_	2	1	4

Final calculation:

$$|1 - 2| + 4 = 5$$

Output: 5

Example 3

Input: moves = "_______"

Step	Character	Left Count	Right Count	Flexible Count
1	_	0	0	1
2	_	0	0	2
3	_	0	0	3
4	_	0	0	4
5	_	0	0	5
6	_	0	0	6
7	_	0	0	7

Final calculation:

$$|0 - 0| + 7 = 7$$

Output: 7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the string once
Space	O(1)	Only a few integer counters are used

The time complexity is linear because we process each character in moves exactly once. Since the string length is n, the runtime scales proportionally with input size.

The space complexity is constant because no extra data structures proportional to input size are allocated. Only three integer counters are maintained regardless of how large the input becomes.

Test Cases

solution = Solution()

assert solution.furthestDistanceFromOrigin("L_RL__R") == 3  # Example 1
assert solution.furthestDistanceFromOrigin("_R__LL_") == 5  # Example 2
assert solution.furthestDistanceFromOrigin("_______") == 7  # Example 3

assert solution.furthestDistanceFromOrigin("L") == 1  # Single left move
assert solution.furthestDistanceFromOrigin("R") == 1  # Single right move
assert solution.furthestDistanceFromOrigin("_") == 1  # Single flexible move

assert solution.furthestDistanceFromOrigin("LR") == 0  # Balanced fixed moves
assert solution.furthestDistanceFromOrigin("LLRR") == 0  # Complete cancellation

assert solution.furthestDistanceFromOrigin("LLL") == 3  # Only left moves
assert solution.furthestDistanceFromOrigin("RRRR") == 4  # Only right moves

assert solution.furthestDistanceFromOrigin("LR__") == 2  # Balanced plus flexible
assert solution.furthestDistanceFromOrigin("LL_R") == 2  # Flexible extends dominant side
assert solution.furthestDistanceFromOrigin("R__") == 3  # Flexible moves reinforce right side

assert solution.furthestDistanceFromOrigin("L_R_R") == 3  # Mixed movement pattern
assert solution.furthestDistanceFromOrigin("LRLRLR___") == 3  # Equal left and right
assert solution.furthestDistanceFromOrigin("LLLL_____") == 9  # Large imbalance plus flexible

Test	Why
"L_RL__R"	Validates the first provided example
"_R__LL_"	Validates the second provided example
"_______"	Ensures all flexible moves are handled correctly
"L"	Smallest input with forced left movement
"R"	Smallest input with forced right movement
"_"	Smallest input with flexible movement
"LR"	Tests perfect cancellation
"LLRR"	Confirms balanced fixed moves return zero
"LLL"	Tests only left movement
"RRRR"	Tests only right movement
"LR__"	Ensures underscores maximize distance
"LL_R"	Checks reinforcement of dominant direction
"R__"	Verifies multiple flexible moves
"L_R_R"	Tests mixed fixed and flexible moves
"LRLRLR___"	Confirms balanced movement plus flexibility
"LLLL_____"	Tests larger imbalance with many underscores

Edge Cases

All Characters Are Underscores

An input such as "_______" can be tricky because there are no forced directions. A naive implementation might mistakenly alternate left and right moves or fail to maximize distance. The correct strategy is to choose the same direction every time, producing the maximum distance equal to the string length. The formula handles this naturally:

$$|0 - 0| + 7 = 7$$

Left and Right Moves Perfectly Cancel Out

Cases such as "LRLR" produce a net displacement of zero from fixed moves. The important observation is that underscores still allow us to move away from the origin. For example, "LR__" should return 2, not 0. Since the implementation adds all flexible moves to the absolute difference, this situation is handled correctly.

No Flexible Moves

When the string contains only 'L' and 'R', such as "LLRRR", there is no optimization choice. The answer simply becomes the absolute difference between right and left counts. The implementation naturally reduces to:

$$|R - L|$$

because the underscore count is zero.

One Direction Strongly Dominates

An input like "LLLL_____" could expose a bug if underscores are assigned inconsistently. Since left movement already dominates, every underscore should also move left to maximize distance. The implementation guarantees this by mathematically adding every flexible move to the existing imbalance instead of simulating moves individually.