#2833

Easy

LeetCode Problem Workspace

Furthest Point From Origin

Determine the maximum distance from origin using string moves and counting underscores optimally for efficient calculation.

string counting

Problem Statement

You are given a string moves of length n containing only 'L', 'R', and '', representing steps on a number line starting at 0. Each character dictates a move: 'L' decreases position by 1, 'R' increases it by 1, and ' ' can be replaced with either 'L' or 'R'.

Return the maximum absolute distance from the origin that can be reached after performing all moves. Decide each '_' replacement to maximize the final distance, considering the effect of counting total left and right moves.

Examples

Example 1

Input: moves = "L_RL__R"

Output: 3

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

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

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

Solution Approach

Count Known Moves

Iterate through the string and tally the number of 'L' and 'R' moves. Keep a separate count of '_' characters to determine the number of flexible moves available.

Determine Optimal Direction

Compare counts of 'L' and 'R'. Replace all underscores with the direction that is currently less frequent if you want to extend in that direction, or the one that maximizes the absolute distance from origin. This ensures maximum displacement on the number line.

Compute Maximum Distance

Sum the absolute difference between total 'L' and 'R' moves plus all flexible underscores applied in the chosen direction. Return this sum as the furthest distance from the origin.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single pass counting moves, and space complexity is O(1) since only counts are stored, not the full string transformations.

What Interviewers Usually Probe

Expect candidates to recognize '_' as a flexible move affecting counting.
Look for a clear approach to replace all underscores with the same direction for maximum effect.
Candidates may fail to consider negative positions; absolute distance matters.

Common Pitfalls or Variants

Common pitfalls

Replacing underscores inconsistently reduces maximum distance.
Counting only 'R' moves or only 'L' moves instead of using absolute difference.
Attempting brute-force string generation instead of counting strategy.

Follow-up variants

Return the actual sequence of moves that produces the furthest distance instead of just the distance.
Handle a 2D grid instead of a 1D number line with 'U', 'D', 'L', 'R' and '_' characters.
Limit the number of underscores that can be replaced to a fixed value k instead of all.

FAQ

What is the Furthest Point From Origin problem about?

It asks you to calculate the maximum distance from origin on a number line given a string of 'L', 'R', and '' moves where ' ' can be replaced optimally.

How should underscores be treated to maximize distance?

All underscores should be replaced with the same move, either 'L' or 'R', depending on which direction increases the absolute distance.

What pattern does this problem follow?

It follows the String plus Counting pattern, focusing on tallying moves and applying flexible positions to maximize result.

Can the input string be very long?

Constraints limit the length to 50, so counting strategy works efficiently in linear time.

What is the expected time complexity?

A single pass counting 'L', 'R', and '_' is sufficient, giving O(n) time and O(1) space complexity.

terminal

Solution

Solution 1: 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.

1

2

3

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        return abs(moves.count("L") - moves.count("R")) + moves.count("_")

Continue Practicing

#2981 find longest special substring that occurs thrice i #2982 find longest special substring that occurs thrice ii #3016 minimum number of pushes to type word ii