387. Furthest Point From Origin

Each '_' independently picks 'L' or 'R'. With k underscores there are 2^k strings; for each one compute the position and take the max absolute value.

Approach

1. Enumerate every assignment of 'L' / 'R' to the k underscore positions (recursive backtracking).
2. For each fully-assigned string, compute count('R') - count('L').
3. Track the maximum absolute value.

Complexity

• Time: O(2^k · n) — exponential in the underscores.
• Space: O(n) — recursion stack and string buffer.

class Solution {
    private int best = 0;

    public int furthestDistanceFromOrigin(String moves) {
        best = 0;
        backtrack(moves, 0, 0);
        return best;
    }

    private void backtrack(String moves, int i, int pos) {
        if (i == moves.length()) {
            best = Math.max(best, Math.abs(pos));
            return;
        }
        char c = moves.charAt(i);
        if (c == 'L') {
            backtrack(moves, i + 1, pos - 1);
        } else if (c == 'R') {
            backtrack(moves, i + 1, pos + 1);
        } else {
            backtrack(moves, i + 1, pos - 1);
            backtrack(moves, i + 1, pos + 1);
        }
    }
}

Forget the brute-force enumeration. The fixed Ls and Rs already pull you a net distance of |R - L|. Each underscore is a free push — and a free push is always best spent in the direction we're already going. So the furthest reachable point is |R - L| + count('_').

Building intuition

Every move shifts you by ±1 on the number line. The Ls and Rs are forced moves; the _s are free choices. Suppose:

• L = number of 'L' characters
• R = number of 'R' characters
• U = number of '_' characters

If we ignore the underscores, the forced moves alone land us at position R - L.

Now the underscores. Each one independently pushes you +1 or -1. To maximise distance from origin:

• If R ≥ L, we're already on the right side — push every underscore right. Final position: (R - L) + U.
• If R < L, we're already on the left side — push every underscore left. Final position: (R - L) - U, whose absolute value is (L - R) + U.

In both cases the answer is |R - L| + U.

Steps

1. Count occurrences of 'L', 'R', and '_' in moves (one linear pass each, or one pass with three counters).
2. Return abs(R - L) + U.

Walk-through

moves = "L_RL__R":

Counts: L = 2, R = 2, U = 3.

|R - L| + U = |2 - 2| + 3 = 3. ✓

Another check, moves = "_R__LL_":

• L = 2, R = 1, U = 4.
• |R - L| + U = 1 + 4 = 5. ✓

moves = "_______" (all free): |0 - 0| + 7 = 7. ✓

Why we can't do better

To go right, every step must be +1. The most +1s we can collect is R + U (all Rs plus every _ voted right) and the fewest -1s we must take is L. So the maximum positive position is R + U - L. Symmetrically, the most negative position is -(L + U - R). The larger of those absolute values is |R - L| + U.

Edge cases

• Single character: "L" → |0 - 1| + 0 = 1. "_" → |0 - 0| + 1 = 1.
• All forced moves: U = 0, answer is |R - L|.

Complexity

• Time: O(n).
• Space: O(1).