Furthest Point From Origin

Easy
560.

Furthest Point From Origin

Furthest Point From Origin is an easy coding problem on strings and greedy, asked in Amazon and Adobe interviews.

You start at position 0 on a number line and are given a string moves of characters 'L', 'R' and '_'.

Each 'L' moves one step left, each 'R' one step right, and each '_' may be taken as either direction.

Return the furthest distance from the origin that can be reached after making all the moves.

Example 1

Input
moves = "L_RL__R"
Output
3
Explanation
Taking every blank as L reaches -3.

Example 2

Input
moves = "_R__LL_"
Output
5

Example 3

Input
moves = "_______"
Output
7
Explanation
All blanks in one direction.

Constraints

  • 1 <= moves.length <= 50
  • moves consists only of 'L', 'R' and '_'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} moves
 * @return {number}
 */
var furthestDistanceFromOrigin = function(moves) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Furthest Point From Origin — Solution in Python, Java & C++

Furthest Point From Origin solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Furthest Point From Origin is an easy coding problem on strings and greedy, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Greedy
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You start at position 0 on a number line and are given a string moves of characters 'L', 'R' and '_'.

Each 'L' moves one step left, each 'R' one step right, and each '_' may be taken as either direction.

Return the furthest distance from the origin that can be reached after making all the moves.

Example 1

Input: moves = "L_RL__R"
Output: 3
Explanation: Taking every blank as L reaches -3.

Example 2

Input: moves = "_R__LL_"
Output: 5

Example 3

Input: moves = "_______"
Output: 7
Explanation: All blanks in one direction.

Constraints

  • 1 <= moves.length <= 50
  • moves consists only of 'L', 'R' and '_'.

Hints for Furthest Point From Origin

  1. Hint 1

    The fixed moves partially cancel: only |L - R| of them survives.

  2. Hint 2

    Every blank should push in the same direction as that surplus.

  3. Hint 3

    So the answer is |L - R| + (number of blanks).

How to solve Furthest Point From Origin

Fixed moves cancel down to a net displacement of |L - R|, and every free move should be spent pushing further out in that same direction.

Approach

  1. Count the 'L', 'R' and '_' characters.
  2. Return |L - R| + blanks.

Why it works

The net position is (R - L) ± blanks. Its magnitude is maximised by aligning all blanks with the sign of R - L, giving |R - L| + blanks. When R == L either direction works and the answer is just the blank count.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting the absolute value gives a negative answer whenever the string leans left.
  • Splitting the blanks between directions is never better — each one contributes a full step outward.

Reference solution

Python

def furthestDistanceFromOrigin(moves: str) -> int:
    l = moves.count('L')
    r = moves.count('R')
    u = moves.count('_')
    return abs(l - r) + u

Java

public static int furthestDistanceFromOrigin(String moves) {
    int l = 0, r = 0, u = 0;
    for (int i = 0; i < moves.length(); i++) {
        char c = moves.charAt(i);
        if (c == 'L') l++;
        else if (c == 'R') r++;
        else u++;
    }
    return Math.abs(l - r) + u;
}

C++

int furthestDistanceFromOrigin(string moves) {
    int l = 0, r = 0, u = 0;
    for (char c : moves) {
        if (c == 'L') l++;
        else if (c == 'R') r++;
        else u++;
    }
    return abs(l - r) + u;
}

JavaScript

var furthestDistanceFromOrigin = function(moves) {
    let l = 0, r = 0, u = 0;
    for (let i = 0; i < moves.length; i++) {
        const c = moves.charAt(i);
        if (c === "L") l++;
        else if (c === "R") r++;
        else u++;
    }
    return Math.abs(l - r) + u;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms