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 <= 50moves consists only of 'L', 'R' and '_'.
Hints for Furthest Point From Origin
Hint 1
The fixed moves partially cancel: only
|L - R|of them survives.Hint 2
Every blank should push in the same direction as that surplus.
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
- Count the
'L','R'and'_'characters. - 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) + uJava
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