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 ith
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)$.
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 |
|