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 _thedistance from the origin of the furthest point you can get to after _n moves.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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 '_'.

Solution

Method 1 – Counting L, R, and Underscores

Intuition

Each ‘L’ moves left, each ‘R’ moves right, and each ‘’ can be used as either. To get the furthest distance, use all ‘’ in one direction (either all left or all right), and add to the count of L or R, whichever is larger.

Approach

  1. Count the number of ‘L’, ‘R’, and ‘_’ in the string.
  2. The furthest distance is abs(count_L - count_R) + count_underscore.
  3. Return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int l = 0, r = 0, u = 0;
        for (char c : moves) {
            if (c == 'L') l++;
            else if (c == 'R') r++;
            else u++;
        }
        return abs(l - r) + u;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

type Solution struct{}
func (Solution) furthestDistanceFromOrigin(moves string) int {
    l, r, u := 0, 0, 0
    for _, c := range moves {
        if c == 'L' {
            l++
        } else if c == 'R' {
            r++
        } else {
            u++
        }
    }
    if l > r {
        return l - r + u
    }
    return r - l + u
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int l = 0, r = 0, u = 0;
        for (char c : moves.toCharArray()) {
            if (c == 'L') l++;
            else if (c == 'R') r++;
            else u++;
        }
        return Math.abs(l - r) + u;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun furthestDistanceFromOrigin(moves: String): Int {
        var l = 0; var r = 0; var u = 0
        for (c in moves) {
            when (c) {
                'L' -> l++
                'R' -> r++
                else -> u++
            }
        }
        return kotlin.math.abs(l - r) + u
    }
}
1
2
3
4
5
6

class Solution:
    def furthestDistanceFromOrigin(self, moves: str) -> int:
        l = moves.count('L')
        r = moves.count('R')
        u = moves.count('_')
        return abs(l - r) + u
1
2
3
4
5
6
7
8

impl Solution {
    pub fn furthest_distance_from_origin(moves: String) -> i32 {
        let l = moves.chars().filter(|&c| c == 'L').count() as i32;
        let r = moves.chars().filter(|&c| c == 'R').count() as i32;
        let u = moves.chars().filter(|&c| c == '_').count() as i32;
        (l - r).abs() + u
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
  furthestDistanceFromOrigin(moves: string): number {
    let l = 0, r = 0, u = 0;
    for (const c of moves) {
      if (c === 'L') l++;
      else if (c === 'R') r++;
      else u++;
    }
    return Math.abs(l - r) + u;
  }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, since each character is processed once.
  • 🧺 Space complexity: O(1), as only counters are used.