Question

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' 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".

 

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:
  def furthestDistanceFromOrigin(self, moves: str) -> int:
    return abs(moves.count("L") - moves.count("R")) + moves.count("_")

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

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