What is the time complexity of the Counting approach?

The time complexity is O(n), where n is the length of the string, as we iterate through the string once.

What is the space complexity of the Counting approach?

The space complexity is O(1) since we only use a few integer variables for counting.

What is the time complexity of the Simulation approach?

The time complexity is O(n), as we process each character in the string exactly once.

What is the space complexity of the Simulation approach?

The space complexity is O(1) because we only maintain a single integer for the position.

Furthest Point From Origin

Difficulty: Easy | Acceptance: 77.00% | Paid: No Topics: String, Counting

You are given a string moves of length n consisting only of characters 'L', 'R', and '_'. The characters 'L' and 'R' represent moves where the object moves one unit to the left or right, respectively. The character '_' represents a move where the object can move either one unit to the left or one unit to the right.

Return the distance from the origin (0) after performing all the moves such that the distance is maximized.

Examples
Constraints
Approach 1: Counting
Approach 2: Simulation

Examples

Input: moves = "L_RL__R"
Output: 3
Explanation: The moves are "L_RL__R". We can replace the '_'s with 'R' to get "LRRLLRR". The distance is 3.

Input: moves = "_R__LL_"
Output: 5
Explanation: The moves are "_R__LL_". We can replace the '_'s with 'R' to get "RRRLLLR". The distance is 5.

Input: moves = "_______"
Output: 7

Constraints

1 <= moves.length <= 100
moves consists only of 'L', 'R', and '_'.

Approach 1: Counting

Intuition Count the net displacement from ‘L’ and ‘R’. The ’_’ characters can always be used to increase the absolute distance from the origin.

Steps

Count the number of ‘L’, ‘R’, and ’_’ characters.
Calculate the base distance as the absolute difference between ‘L’ and ‘R’ counts.
Add the count of ’_’ to the base distance to get the maximum distance.

python

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -&gt; int:
        l = moves.count('L')
        r = moves.count('R')
        u = moves.count('_')
        return abs(l - r) + u

Complexity

Time: O(n)
Space: O(1)
Notes: Efficient single pass solution.

Approach 2: Simulation

Intuition Simulate the movement step-by-step. For fixed moves, move accordingly. For wildcards, move in the direction that increases the distance from 0.

Steps

Initialize a position variable to 0.
Iterate through each character in the string.
If ‘L’, decrement position. If ‘R’, increment position.
If ’_’, check the current position. If positive, move right; otherwise, move left.
Return the absolute value of the final position.

python

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -&gt; int:
        pos = 0
        for c in moves:
            if c == 'L':
                pos -= 1
            elif c == 'R':
                pos += 1
            else:
                if pos &gt; 0:
                    pos += 1
                else:
                    pos -= 1
        return abs(pos)

Complexity

Time: O(n)
Space: O(1)
Notes: Intuitive simulation approach.