We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Furthest Point From Origin

Number: 3019

Difficulty: Easy

Paid? No

Companies: Amazon, Barclays

Problem Description

Given a string moves that represents movements on a number line (starting from 0), where each character is either 'L', 'R', or '_' representing a move left, move right, or an uncertain move (which you can decide to move left or right), determine the maximum possible distance from the origin that you can achieve after processing all moves.

Key Insights

  • Count the number of definite left moves ('L') and right moves ('R').
  • Count the number of uncertain moves ('_').
  • To maximize the distance from the origin, use all uncertain moves in the same direction that creates the larger difference.
  • The final distance is the sum of the absolute difference between definite left/right moves and all uncertain moves.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the moves string (iterating through the string once).
Space Complexity: O(1), using only constant extra space.

Solution

The solution involves iterating through the moves string and counting the definite left and right moves along with the uncertain moves. After counting:

  1. Compute the difference between the counts of right and left moves.
  2. Add all uncertain moves to this difference, as you can direct all uncertain moves to the side that increases the distance.
  3. The absolute sum yields the furthest possible distance from the origin.

Code Solutions

# Python implementation

def furthestDistanceFromOrigin(moves: str) -> int:
    # Count definite left and right moves using count() method.
    left_moves = moves.count('L')
    right_moves = moves.count('R')
    uncertain_moves = moves.count('_')
    
    # Maximum distance is the absolute difference of definite moves plus all uncertain moves.
    return abs(right_moves - left_moves) + uncertain_moves

# Example usage:
if __name__ == "__main__":
    moves = "L_RL__R"
    print(furthestDistanceFromOrigin(moves))  # Output: 3
← Back to All Questions