Welcome to Subscribe On Youtube
2833. Furthest Point From Origin
Description
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^{th}
move, you can choose one of the following directions:
 move to the left if
moves[i] = 'L'
ormoves[i] = '_'
 move to the right if
moves[i] = 'R'
ormoves[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'_'
.
Solutions
Solution 1: Greedy
When encountering the character ‘’, we can choose to move left or right. The problem requires us to find the farthest point from the origin. Therefore, we can first traverse once, greedily move all ‘’ to the left, and find the farthest point from the origin at this time. Then traverse again, greedily move all ‘_’ to the right, and find the farthest point from the origin at this time. Finally, take the maximum of the two traversals.
Further, we only need to calculate the difference between the number of ‘L’ and ‘R’ in the string, and then add the number of ‘_’.
The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.

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; } }

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('_'); } };

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

func furthestDistanceFromOrigin(moves string) int { count := func(c string) int { return strings.Count(moves, c) } return abs(count("L")count("R")) + count("_") } func abs(x int) int { if x < 0 { return x } return x }

function furthestDistanceFromOrigin(moves: string): number { const count = (c: string) => moves.split('').filter(x => x === c).length; return Math.abs(count('L')  count('R')) + count('_'); }