Furthest Point From Origin

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 i<sup>th</sup> 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".

Naive Solution

The most straightforward approach is to explore all possible combinations of left and right moves for the underscores and find the maximum distance. This can be done recursively, trying both 'L' and 'R' for each underscore and keeping track of the maximum absolute value of the final position.

def furthest_distance_naive(moves):
    n = len(moves)
    max_dist = 0

    def solve(index, current_pos):
        nonlocal max_dist
        if index == n:
            max_dist = max(max_dist, abs(current_pos))
            return

        if moves[index] == 'L':
            solve(index + 1, current_pos - 1)
        elif moves[index] == 'R':
            solve(index + 1, current_pos + 1)
        else:
            solve(index + 1, current_pos - 1)  # Try 'L'
            solve(index + 1, current_pos + 1)  # Try 'R'

    solve(0, 0)
    return max_dist

# Example Usage
moves1 = "L_RL__R"
print(furthest_distance_naive(moves1))  # Output: 3

moves2 = "_R__LL_"
print(furthest_distance_naive(moves2))  # Output: 5

moves3 = "_______"
print(furthest_distance_naive(moves3))  # Output: 7

Optimal Solution

The optimal solution leverages the observation that to maximize the distance from the origin, we want to move all underscores either to the left or to the right. We can calculate the distance by assuming all underscores move to the right and then calculate the distance by assuming all underscores move to the left. The maximum of the absolute values of these two distances is the furthest distance possible.

def furthest_distance_optimal(moves):
    left_right_moves = 0
    underscores = 0

    for move in moves:
        if move == 'L':
            left_right_moves -= 1
        elif move == 'R':
            left_right_moves += 1
        else:
            underscores += 1

    return max(abs(left_right_moves + underscores), abs(left_right_moves - underscores))

# Example Usage
moves1 = "L_RL__R"
print(furthest_distance_optimal(moves1))  # Output: 3

moves2 = "_R__LL_"
print(furthest_distance_optimal(moves2))  # Output: 5

moves3 = "_______"
print(furthest_distance_optimal(moves3))  # Output: 7

Big(O) Runtime Analysis

The optimal solution iterates through the string once. Therefore, the runtime complexity is O(n), where n is the length of the moves string.

Big(O) Space Usage Analysis

The optimal solution uses only a few integer variables, irrespective of the input size. Thus, the space complexity is O(1), i.e., constant space.

Edge Cases

1. Empty String:
   • If the input string is empty, the function should return 0, as there are no moves to make.
2. String with No Underscores:
   • If the string contains only 'L' and 'R', the algorithm still works correctly. It calculates the net displacement based on these moves.
3. String with Only Underscores:
   • If the string contains only underscores, the algorithm treats them as all moving in one direction or the other.
4. Very Large Number of Underscores:
   • The algorithm handles a large number of underscores correctly since it only performs simple arithmetic operations on integers.