# Furthest Point From Origin
**Difficulty:** EASY
[External](https://leetcode.com/problems/furthest-point-from-origin)
Canonical: https://scaleengineer.com/dsa/problems/furthest-point-from-origin
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** String
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays)
---
## Problem
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 `'_'`.

# Approaches
## Brute-Force Recursive Approach
This approach explores every possible outcome by treating each underscore `_` as a decision point. For each `_`, we can either move left or move right. A recursive function can be used to explore all these paths. The function would take the current index in the `moves` string and the current position on the number line as parameters. When an `_` is encountered, the function makes two recursive calls: one for moving left and one for moving right. The final result is the maximum absolute position found among all possible paths.
**Time:** O(2^k), where `k` is the number of `_` characters in the `moves` string. In the worst case, the entire string consists of `_`, so `k=n`, leading to `O(2^n)`. This is because for each `_`, the number of computation paths doubles. · **Space:** O(n), where n is the length of the `moves` string. This is due to the maximum depth of the recursion stack.
**Pros:** Simple to understand and implement the logic of exploring all possibilities.; Correctly solves the problem for small inputs.
**Cons:** Highly inefficient. The exponential time complexity makes it infeasible for larger inputs (e.g., `n=50`). It will result in a "Time Limit Exceeded" error on most platforms.
### Explanation
The core idea is to build a recursive function, say `findMaxDistance(index, currentPosition)`.

- **Base Case:** When the `index` reaches the end of the `moves` string, it means we have processed all moves. We return the absolute value of the `currentPosition`, which represents the distance from the origin for one complete path.
- **Recursive Step:**
  - For a given `index`, we look at `moves.charAt(index)`.
  - If it's 'L', we decrement the position and recurse: `findMaxDistance(index + 1, currentPosition - 1)`.
  - If it's 'R', we increment the position and recurse: `findMaxDistance(index + 1, currentPosition + 1)`.
  - If it's '_', we have a choice. We must explore both possibilities to find the maximum possible distance.
    - Move Left: `distanceLeft = findMaxDistance(index + 1, currentPosition - 1)`.
    - Move Right: `distanceRight = findMaxDistance(index + 1, currentPosition + 1)`.
    - We return the maximum of the two outcomes: `Math.max(distanceLeft, distanceRight)`.
- The initial call to the function would be `findMaxDistance(0, 0)`.

```java
class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        return findMaxDistance(moves, 0, 0);
    }

    private int findMaxDistance(String moves, int index, int currentPosition) {
        // Base case: we've processed all moves
        if (index == moves.length()) {
            return Math.abs(currentPosition);
        }

        char move = moves.charAt(index);
        if (move == 'L') {
            return findMaxDistance(moves, index + 1, currentPosition - 1);
        } else if (move == 'R') {
            return findMaxDistance(moves, index + 1, currentPosition + 1);
        } else { // move == '_'
            // Explore both possibilities and return the one that leads to a further distance
            int distIfLeft = findMaxDistance(moves, index + 1, currentPosition - 1);
            int distIfRight = findMaxDistance(moves, index + 1, currentPosition + 1);
            return Math.max(distIfLeft, distIfRight);
        }
    }
}
```
### Algorithm
- Define a recursive function `findMaxDistance(moves, index, currentPosition)`.
- If `index` equals the length of `moves`, return `abs(currentPosition)`.
- Get the character `move` at the current `index`.
- If `move` is 'L', recursively call `findMaxDistance(moves, index + 1, currentPosition - 1)`.
- If `move` is 'R', recursively call `findMaxDistance(moves, index + 1, currentPosition + 1)`.
- If `move` is '_', make two recursive calls: one for moving left (`currentPosition - 1`) and one for moving right (`currentPosition + 1`). Return the maximum of the results from these two calls.
- Start the process by calling `findMaxDistance(moves, 0, 0)`.

## Dynamic Programming with Memoization
The brute-force recursive approach suffers from re-computing the same subproblems multiple times. For example, `findMaxDistance(index, position)` might be called with the same `index` and `position` through different paths. We can optimize this by storing the results of these subproblems in a cache or a memoization table. This technique is known as Dynamic Programming.
**Time:** O(n^2), where `n` is the length of `moves`. The number of states is `n * (2n+1)`, which is `O(n^2)`. Each state is computed once. · **Space:** O(n^2) for the memoization table. The recursion stack depth adds `O(n)`, but it's dominated by the table size.
**Pros:** Much more efficient than the brute-force approach.; Guaranteed to pass within time limits for the given constraints (`n <= 50`).
**Cons:** Uses significant space (`O(n^2)`).; More complex to implement than the optimal single-pass solution.
### Explanation
The state of our subproblem can be defined by `(index, currentPosition)`. We want to find the maximum distance from the origin we can achieve starting from `index` with a `currentPosition`.

We use a 2D array, `memo`, to store the results. `memo[index][position]` will store the result for `findMaxDistance(index, position)`. The `position` can be negative, so we need to offset it to use it as an array index. Since the position can range from `-n` to `n`, we can use an offset of `n`. So, `memo[index][position + n]` will be used.

The recursive function is modified to check the memoization table before computing.

```java
class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int n = moves.length();
        // memo[index][position + n]
        Integer[][] memo = new Integer[n + 1][2 * n + 1];
        return findMaxDistance(moves, 0, 0, memo);
    }

    private int findMaxDistance(String moves, int index, int currentPosition, Integer[][] memo) {
        int n = moves.length();
        // Base case
        if (index == n) {
            return Math.abs(currentPosition);
        }
        
        // Check memoization table (position is offset by n)
        if (memo[index][currentPosition + n] != null) {
            return memo[index][currentPosition + n];
        }

        char move = moves.charAt(index);
        int result;
        if (move == 'L') {
            result = findMaxDistance(moves, index + 1, currentPosition - 1, memo);
        } else if (move == 'R') {
            result = findMaxDistance(moves, index + 1, currentPosition + 1, memo);
        } else { // move == '_'
            int distIfLeft = findMaxDistance(moves, index + 1, currentPosition - 1, memo);
            int distIfRight = findMaxDistance(moves, index + 1, currentPosition + 1, memo);
            result = Math.max(distIfLeft, distIfRight);
        }
        
        // Store result in memo and return
        memo[index][currentPosition + n] = result;
        return result;
    }
}
```
This ensures that each subproblem `(index, position)` is solved only once.
### Algorithm
- Create a 2D memoization table `memo` of size `(n+1) x (2n+1)` to store results of subproblems, initialized to a null/sentinel value.
- Define a recursive function `findMaxDistance(moves, index, position, memo)`.
- The position can range from `-n` to `n`. Use an offset of `n` to map it to a valid array index `position + n`.
- **Base Case:** If `index == moves.length()`, return `abs(position)`.
- **Memoization Check:** If `memo[index][position + n]` is already computed, return it.
- **Recursive Step:** Compute the result based on `moves.charAt(index)` as in the brute-force approach.
- **Store Result:** Store the computed result in `memo[index][position + n]` before returning.
- The initial call is `findMaxDistance(moves, 0, 0, memo)`.

## Single Pass Greedy Approach
A closer look at the problem reveals a greedy strategy. To maximize the distance from the origin, we want to go as far as possible in one direction (either all the way to the right or all the way to the left). Any `_` move can be used to contribute to this one-directional push. The fixed 'L' and 'R' moves establish a base displacement. All the flexible `_` moves should then be used to augment this displacement in the direction that leads further from the origin.
**Time:** O(n), where `n` is the length of the `moves` string. We perform a single pass over the string. · **Space:** O(1). We only use a few variables to store the counts, regardless of the input size.
**Pros:** Extremely efficient in both time and space.; Simple and elegant solution.
**Cons:** Requires a key insight that might not be immediately obvious. The greedy choice needs to be justified.
### Explanation
The key insight is that to achieve the maximum distance, all `_` characters must be resolved to the same direction: either all become 'L' or all become 'R'.

- Let's count the number of 'L', 'R', and '_' characters in the string. Let these be `countL`, `countR`, and `countUnderscore`.
- The net displacement from the fixed moves ('L' and 'R') is `countR - countL`.
- Now, we have `countUnderscore` moves that we can choose.
  - **Scenario 1: Go as far right as possible.** We treat every `_` as an 'R'. The final position would be `(countR - countL) + countUnderscore`.
  - **Scenario 2: Go as far left as possible.** We treat every `_` as an 'L'. The final position would be `(countR - countL) - countUnderscore`.
- The furthest distance from the origin is the maximum of the absolute values of these two potential final positions.
- `max_distance = Math.max(Math.abs((countR - countL) + countUnderscore), Math.abs((countR - countL) - countUnderscore))`
- This can be simplified. Let `base = countR - countL` and `flex = countUnderscore`. We need `max(abs(base + flex), abs(base - flex))`. This expression is mathematically equivalent to `abs(base) + flex`.
- So, the final answer is simply `Math.abs(countR - countL) + countUnderscore`.
- The algorithm is to iterate through the string once to get the counts, and then apply this formula.

```java
class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int countL = 0;
        int countR = 0;
        int countUnderscore = 0;

        for (char move : moves.toCharArray()) {
            if (move == 'L') {
                countL++;
            } else if (move == 'R') {
                countR++;
            } else {
                countUnderscore++;
            }
        }

        // The furthest we can go right is (countR - countL) + countUnderscore
        // The furthest we can go left is (countR - countL) - countUnderscore
        // The distance is the max of the absolute values of these two positions.
        // This simplifies to abs(countR - countL) + countUnderscore.
        
        int baseDisplacement = countR - countL;
        return Math.abs(baseDisplacement) + countUnderscore;
    }
}
```
### Algorithm
- Initialize three counters: `countL = 0`, `countR = 0`, `countUnderscore = 0`.
- Iterate through the `moves` string once.
- For each character, increment the corresponding counter.
- After the loop, calculate the net displacement from fixed moves: `baseDisplacement = countR - countL`.
- The maximum distance is the absolute value of the base displacement plus the number of flexible moves: `Math.abs(baseDisplacement) + countUnderscore`.
- Return this value.

# Solutions
### Java

```java
class Solution {
public
  int furthestDistanceFromOrigin(String moves) {
    return Math.abs(count(moves, 'L') - count(moves, 'R')) + count(moves, '_');
  }
private
  int count(String s, char c) {
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == c) {
        ++cnt;
      }
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int furthestDistanceFromOrigin(string moves) {
    auto cnt = [&](char c) { return count(moves.begin(), moves.end(), c); };
    return abs(cnt('L') - cnt('R')) + cnt('_');
  }
};

```

### Python

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

```