Furthest Point From Origin - Video Solutions

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.