Scale Engineer

Furthest Point From Origin

Easy
#2533Time: O(2^k), where `k` is the number of `_` characters in the `moves` string. In the worst case, the entire string consists of `_`, so `k=n`, leading to `O(2^n)`. This is because for each `_`, the number of computation paths doubles.Space: O(n), where n is the length of the `moves` string. This is due to the maximum depth of the recursion stack.1 company
Patterns
Counting
Data structures
String
Companies
Barclays

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores every possible outcome by treating each underscore _ as a decision point. For each _, we can either move left or move right. A recursive function can be used to explore all these paths. The function would take the current index in the moves string and the current position on the number line as parameters. When an _ is encountered, the function makes two recursive calls: one for moving left and one for moving right. The final result is the maximum absolute position found among all possible paths.

Algorithm

  • Define a recursive function findMaxDistance(moves, index, currentPosition).
  • If index equals the length of moves, return abs(currentPosition).
  • Get the character move at the current index.
  • If move is 'L', recursively call findMaxDistance(moves, index + 1, currentPosition - 1).
  • If move is 'R', recursively call findMaxDistance(moves, index + 1, currentPosition + 1).
  • If move is '_', make two recursive calls: one for moving left (currentPosition - 1) and one for moving right (currentPosition + 1). Return the maximum of the results from these two calls.
  • Start the process by calling findMaxDistance(moves, 0, 0).

Walkthrough

The core idea is to build a recursive function, say findMaxDistance(index, currentPosition).

  • Base Case: When the index reaches the end of the moves string, it means we have processed all moves. We return the absolute value of the currentPosition, which represents the distance from the origin for one complete path.
  • Recursive Step:
    • For a given index, we look at moves.charAt(index).
    • If it's 'L', we decrement the position and recurse: findMaxDistance(index + 1, currentPosition - 1).
    • If it's 'R', we increment the position and recurse: findMaxDistance(index + 1, currentPosition + 1).
    • If it's '_', we have a choice. We must explore both possibilities to find the maximum possible distance.
      • Move Left: distanceLeft = findMaxDistance(index + 1, currentPosition - 1).
      • Move Right: distanceRight = findMaxDistance(index + 1, currentPosition + 1).
      • We return the maximum of the two outcomes: Math.max(distanceLeft, distanceRight).
  • The initial call to the function would be findMaxDistance(0, 0).
class Solution {    public int furthestDistanceFromOrigin(String moves) {        return findMaxDistance(moves, 0, 0);    }     private int findMaxDistance(String moves, int index, int currentPosition) {        // Base case: we've processed all moves        if (index == moves.length()) {            return Math.abs(currentPosition);        }         char move = moves.charAt(index);        if (move == 'L') {            return findMaxDistance(moves, index + 1, currentPosition - 1);        } else if (move == 'R') {            return findMaxDistance(moves, index + 1, currentPosition + 1);        } else { // move == '_'            // Explore both possibilities and return the one that leads to a further distance            int distIfLeft = findMaxDistance(moves, index + 1, currentPosition - 1);            int distIfRight = findMaxDistance(moves, index + 1, currentPosition + 1);            return Math.max(distIfLeft, distIfRight);        }    }}

Complexity

Time

O(2^k), where `k` is the number of `_` characters in the `moves` string. In the worst case, the entire string consists of `_`, so `k=n`, leading to `O(2^n)`. This is because for each `_`, the number of computation paths doubles.

Space

O(n), where n is the length of the `moves` string. This is due to the maximum depth of the recursion stack.

Trade-offs

Pros

  • Simple to understand and implement the logic of exploring all possibilities.

  • Correctly solves the problem for small inputs.

Cons

  • Highly inefficient. The exponential time complexity makes it infeasible for larger inputs (e.g., n=50). It will result in a "Time Limit Exceeded" error on most platforms.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem