algoadvance

Leetcode 2833. Furthest Point From Origin

Problem Statement

Given a string moves that represents the movement instructions of a character starting at the origin (0,0) on a 2D plane, return the maximum distance the character can be from the origin after executing the given moves.

The string moves consists of characters 'L' (left), 'R' (right), or '_' (either left or right).

Clarifying Questions

  1. Q: Can the _ character be replaced by either L or R to maximize the distance from the origin?
    • A: Yes, '_ ' can be replaced with either 'L' or 'R'.
  2. Q: Are there any limits on the length of the string moves?
    • A: While the problem doesn’t specify, typical interview constraints might range from 1 to 10,000 or so.
  3. Q: Can there be any invalid characters in the string?
    • A: No, the problem guarantees that the string only contains 'L', 'R', or '_'.

Strategy

To maximize the distance from the origin, we need to understand the effect of each character:

  1. 'L' moves the character 1 unit left (towards the negative x-axis).
  2. 'R' moves the character 1 unit right (towards the positive x-axis).
  3. '_ ' can move the character either left or right. To maximize the distance, each '_ ' should move in the direction that currently increases the net displacement further.

The steps are:

  1. Compute the net displacement from all 'L' and 'R' moves.
  2. Add the number of '_ ' moves to the absolute value of this net displacement to maximize it.

Code

public class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int leftCount = 0;
        int rightCount = 0;
        int underscoreCount = 0;
        
        for (char move : moves.toCharArray()) {
            if (move == 'L') {
                leftCount++;
            } else if (move == 'R') {
                rightCount++;
            } else {
                underscoreCount++;
            }
        }
        
        int netDisplacement = Math.abs(leftCount - rightCount);
        return netDisplacement + underscoreCount;
    }
}

Explanation

  1. Initialization: We initialize three counters, leftCount, rightCount, and underscoreCount, to 0.
  2. Counting Loops: We iterate over the moves string and increment the counters based on whether the character is 'L', 'R', or '_'.
  3. Net Displacement Calculation: We calculate the net displacement from the number of left and right moves using Math.abs(leftCount - rightCount).
  4. Maximum Distance: We add the number of underscores to the net displacement to get the furthest distance possible, as each underscore can be used to further either direction.

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string moves. We traverse the string once to count each type of move, making the solution efficient and optimal for large inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI