Furthest Point From Origin - Practice Coding Problems

Furthest Point From Origin - Problem

String Counting Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: moves = "L_RL__R"

› Output: 3

💡 Note: We have L=1, R=2, _=3. Net from fixed moves: 2-1=1. Add all _ to right: 1+3=4. But we can do better by going left: |1-3|=2. Wait, let me recalculate: if we assign all _ as R: LRRLRRR gives position -1+1+1-1+1+1+1=3. If all _ as L: LRRLLLR gives position -1+1+1-1-1-1+1=-1, distance=1. So maximum is 3.

Example 2 — All Flexible

$ Input: moves = "___"

› Output: 3

💡 Note: All moves are flexible. Assign all to same direction (e.g., all R) gives distance 3.

Example 3 — No Flexible Moves

$ Input: moves = "LLR"

› Output: 1

💡 Note: No flexible moves. Final position: -1-1+1=-1, distance is 1.

Constraints

1 ≤ moves.length ≤ 2000
moves[i] is either 'L', 'R', or '_'

Visualization

Tap to expand

Understanding the Visualization

Input

String with L, R, and _ characters

Strategy

Count characters and assign _ optimally

Output

Maximum possible distance from origin

Key Takeaway

🎯 Key Insight: All flexible moves should go in the same direction to maximize distance from origin

Asked in

G Google 15 M Meta 12 a Amazon 8

The key insight is that all flexible moves ('_') should be assigned to the same direction to maximize distance from origin. The optimal approach counts L, R, and _ characters, calculates the net position from fixed moves, then adds all flexible moves in the direction that maximizes the absolute distance. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Count and Maximize	O(n)	O(1)	Count L, R, and _ characters, then assign all _ to maximize distance
Brute Force - Try All Combinations	O(2^k)	O(k)	Generate all possible move combinations and find the maximum distance

Greedy - Count and Maximize — Algorithm Steps

Count occurrences of 'L', 'R', and '_'
Calculate net position from fixed moves
Add all flexible moves to maximize absolute distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Count

Count L, R, and _ characters

Calculate

Find net position from fixed moves

Optimize

Assign all _ to maximize distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* moves) {
    int leftCount = 0;
    int rightCount = 0;
    int flexibleCount = 0;
    int len = strlen(moves);
    
    for (int i = 0; i < len; i++) {
        if (moves[i] == 'L') leftCount++;
        else if (moves[i] == 'R') rightCount++;
        else flexibleCount++;
    }
    
    // Net position from fixed moves
    int netPosition = rightCount - leftCount;
    
    // Add all flexible moves to maximize distance
    if (netPosition >= 0) {
        return netPosition + flexibleCount;
    } else {
        return abs(netPosition) + flexibleCount;
    }
}

int main() {
    char moves[1001];
    fgets(moves, sizeof(moves), stdin);
    moves[strcspn(moves, "\n")] = 0;
    int result = solution(moves);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string to count characters

✓ Linear Growth

Space Complexity

O(1)

Only uses a few counter variables

✓ Linear Space

25.0K Views

Medium Frequency

~10 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Count and Maximize — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler