Maximize Final Distance After Fixed and Flexible Moves
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Maximize Final Distance After Fixed and Flexible Moves
You start at coordinate `0` on a number line. String `moves` has length `n` and contains only `'L'`, `'R'`, and `'_'`.
Process its characters in order, taking one unit step each time:
- `'L'` requires a step to the left.
- `'R'` requires a step to the right.
- `'_'` allows you to choose either direction for that step.
Return the greatest distance from the origin you can achieve after all `n` moves.
### Examples
**Example 1**
```text
Input: moves = "RR_L_"
Output: 3
```
Choose right for both flexible moves, obtaining `"RRRLR"`. The successive coordinates are `1,2,3,2,3`, so the final distance is `3`. No choice achieves a greater final distance.
**Example 2**
```text
Input: moves = "LL_RL_"
Output: 4
```
Choose left for both flexible moves, obtaining `"LLLRLL"`. This ends at coordinate `-4`, at distance `4` from the origin, which is maximal.
### Constraints
- `1 <= moves.length == n <= 50`.
- `moves` contains only `'L'`, `'R'`, and `'_'`.
### Clarifying Questions
- Is the requested value a signed coordinate? No; return its nonnegative distance from zero.
- Is the objective the largest distance visited at any time? No; consider the position after all moves.
- Can a fixed `'L'` or `'R'` be changed? No; only `'_'` permits a choice.
- Must different underscores choose different directions? No; every flexible step can choose left or right independently.
### C++ Interface
```cpp
class Solution {
public:
int furthestDistanceFromOrigin(string moves) {
}
};
```
### Reasoning Checkpoints
- Keep the final-position objective separate from distances at intermediate times.
- Account for both possible sides of the origin.
- Justify that your chosen flexible steps attain the claimed maximum.
```hint Fixed displacement
What final displacement comes from the fixed moves alone, and how far can the flexible moves change it?
```
Overview: Choose the directions of flexible number-line moves to maximize the distance from zero after every fixed and flexible step has been taken.