2833. Furthest Point From Origin

題目 / Problem

中文 給你一個長度為 n 的字串 moves，只包含字元 'L'、'R' 與 '_'。你從數線上的原點 0 出發，第 i 步可以： - 當 moves[i] == 'L' 或 '_' 時，往左移動一格 - 當 moves[i] == 'R' 或 '_' 時，往右移動一格

請回傳「在走完 n 步之後，能到達距離原點最遠的點」的距離。

English You are given a string moves of length n containing only 'L', 'R', and '_'. Starting at 0 on a number line, at step i: - If moves[i] is 'L' or '_', you may move left by 1 - If moves[i] is 'R' or '_', you may move right by 1

Return the distance from the origin of the furthest point you can reach.

Constraints - 1 <= moves.length == n <= 50 - moves consists only of 'L', 'R', '_'

Example moves = "L_RL__R" → output 3. One optimal sequence is "LLRLLLR", ending at -3, so the distance is 3.

名詞解釋 / Glossary

• Distance from origin / 距離原點：數線上一點 x 到 0 的距離，即 |x|（絕對值）。On a number line, the distance from point x to 0 is |x| (absolute value).
• Counting / 計數：把一個字串依每種字元分類並計算出現次數，是最基本的統計技巧。Tallying occurrences of each character — one of the simplest string techniques.
• Greedy choice / 貪心選擇：在每一步都做對「最終答案」最有利的決定，且可以證明這些局部決定合成全局最佳解。Make the locally best decision at each step when it provably combines into the globally best answer.
• Absolute value / 絕對值：|x|，表示忽略正負號之後的大小。C 中使用 abs(x)（需要 <stdlib.h>）；C++ 可以用 std::abs。|x|, the magnitude ignoring sign. In C use abs(x) (from <stdlib.h>); in C++ use std::abs.
• size_t / 無號長度型別：C/C++ 用來表示長度與索引的無號整數型別，由 <stddef.h> / <cstddef> 提供。Unsigned integer type used for sizes and indices.
• Range-for loop / 範圍式 for 迴圈：C++11 的 for (char c : s) 語法，會依序走訪容器中每一個元素。C++11 syntax that iterates each element of a container without manual indexing.

思路

把問題拆開來看：每一個 '_' 可以自由選擇左或右，其餘字元方向固定。設 L 是固定向左的數量、R 是固定向右的數量、U 是 '_' 的數量。最終位置是「右的步數減左的步數」，我們想要 |final_position| 越大越好。暴力法會枚舉 2^U 種指派方式，當 U 稍大就會爆炸。關鍵觀察（來自提示）是：要讓絕對值最大，所有 '_' 應該朝同一方向走——如果有任何一個 '_' 朝反方向走，就等於在抵消已有的偏移，答案一定不會變大。既然統一方向，就挑「原本已經比較多的那一邊」繼續加碼：若 L ≥ R，全部 '_' 走左，最終位置是 -(L + U - R)，距離是 L + U - R；若 R > L 則對稱得到 R + U - L。兩種情況合成一式，答案就是 |L - R| + U。只要掃一次字串做計數即可，O(n) 時間、O(1) 空間。

Break the problem apart: each '_' is free to go either way, and every other character is forced. Let L, R, U be the counts of 'L', 'R', '_'. The final position equals (rights − lefts), and we want |final_position| as large as possible. A brute force would try all 2^U assignments — exponential. The hint nails the key insight: to maximize the absolute value, all '_' should point in the same direction; sending even one the other way partially cancels the offset you already built up, which can never help. Given that, aim the entire '_' block at whichever side already has more forced moves. If L ≥ R, every '_' goes left and the final position is −(L + U − R), giving distance L + U − R; symmetrically, if R > L, the distance is R + U − L. Both cases collapse to |L − R| + U. One pass over the string, O(n) time and O(1) space.

逐步走查 / Walkthrough

用範例一 moves = "L_RL__R"（長度 7）走一遍，維護三個計數器 L、R、U：

掃完後 L = 2、R = 2、U = 3。答案 = |L − R| + U = |2 − 2| + 3 = 3。對應到字串，把兩個 '_'（位置 1）與兩個 '_'（位置 4、5）都選成同一個方向（例如全部向左），就得到解釋中的 "LLRLLLR"，最終落在 −3，距離為 3。✅

Running through "L_RL__R" with counters L, R, U: after the full pass we have L = 2, R = 2, U = 3. Plugging in: |2 − 2| + 3 = 3. That matches the sample’s "LLRLLLR" trajectory landing at −3.

Solution — C

// 演算法：統計 'L'、'R'、'_' 的個數，答案 = |L - R| + U。
// Algorithm: count 'L', 'R', '_'; the answer is |L - R| + U.
// 正確性來自「所有 '_' 應走同一方向」的貪心觀察。
// Correctness follows from the greedy observation that all '_' go the same way.

#include <stdlib.h>  // 提供 abs() / provides abs()

int furthestDistanceFromOrigin(char* moves) {
    // 三個計數器：固定向左、固定向右、可自由選擇的底線。
    // Three counters: forced-left, forced-right, free underscores.
    int left = 0, right = 0, underscore = 0;

    // 逐字元掃描直到遇到字串結尾的 ''。
    // Walk char by char until we hit the C-string terminator ''.
    // 這裡 *moves 是「moves 目前指到的那個字元」，再把指標往後移一格。
    // Here *moves dereferences the pointer to read the current char, then we advance.
    for (char* p = moves; *p != ''; ++p) {
        if (*p == 'L') {            // 向左固定一步 / a forced left step
            ++left;                 // 左邊計數 +1 / bump the left counter
        } else if (*p == 'R') {     // 向右固定一步 / a forced right step
            ++right;                // 右邊計數 +1 / bump the right counter
        } else {                    // 其餘只會是 '_' / the only remaining char is '_'
            ++underscore;           // 自由步數 +1 / one more free step
        }
    }

    // |L - R| 表示固定步數造成的偏移，再加上 underscore 表示所有底線都投向同側。
    // |L - R| is the offset from forced moves; adding underscore sends every '_' the same way.
    return abs(left - right) + underscore;
}

Solution — C++

// 演算法與 C 版相同：計數 L、R、_，回傳 |L - R| + U。
// Same algorithm as the C version: count L, R, _, return |L - R| + U.
// 這裡用 range-for 與 std::abs 讓程式碼更貼近現代 C++ 風格。
// Here we use a range-for loop and std::abs for idiomatic modern C++.

#include <string>     // std::string
#include <cstdlib>    // std::abs (整數版本) / integer abs

class Solution {
public:
    int furthestDistanceFromOrigin(std::string moves) {
        // 初始化三個計數器為 0 / initialize the three counters to 0
        int left = 0, right = 0, underscore = 0;

        // range-for：依序拿到每一個字元的副本 c，不用寫索引。
        // range-for: gives us each character c in turn, no manual index needed.
        for (char c : moves) {
            if (c == 'L') {            // 固定向左 / forced left
                ++left;                // 左計數 +1 / bump left
            } else if (c == 'R') {     // 固定向右 / forced right
                ++right;               // 右計數 +1 / bump right
            } else {                   // 其餘必為 '_' / otherwise it must be '_'
                ++underscore;          // 自由步數 +1 / bump the free counter
            }
        }

        // std::abs 取整數絕對值；加上 underscore 代表所有 '_' 都朝同一側。
        // std::abs gives the integer magnitude; adding underscore aims every '_' the same way.
        return std::abs(left - right) + underscore;
    }
};

複雜度 / Complexity

• Time: O(n) — 只掃字串一次做計數，n 是 moves 的長度；沒有巢狀迴圈。We scan the string exactly once; n is the length of moves, and there is no nested work.
• Space: O(1) — 只用了三個 int 計數器，不隨輸入長度成長。Just three integer counters; memory usage is constant regardless of n.

Pitfalls & Edge Cases

• 忘了加上 U（底線數）/ Forgetting to add U：只回傳 |L - R| 會漏掉所有自由步數。程式碼最後明確地 + underscore。Returning only |L - R| misses the free moves; the final expression explicitly adds underscore.
• 符號搞錯 / Sign confusion：結果可能是負方向的最遠點（例如例 1 落在 -3），但題目要的是「距離」，所以一定要取絕對值。The furthest point may be negative, but the answer is a distance — always take the absolute value.
• 試圖貪心把 '_' 分兩邊走 / Splitting '_' between both sides：會相互抵消，距離變小。正確貪心是「全部同方向」，在證明這一點之前很容易寫錯。Splitting underscores cancels offsets and shrinks the answer; the correct greedy is to send all underscores the same direction.
• 空字串 / Empty input：約束保證 n ≥ 1，但即使 n = 0，三個計數器都是 0，函式會回 0，行為仍正確。Constraints guarantee n ≥ 1, but even with an empty string the counters stay 0 and the function correctly returns 0.
• C 字串結尾 / C-string termination：C 版用 *p != '\0' 判斷結束，不要誤用 strlen 多掃一次字串，那會白花一次 O(n)。The C version stops at the null terminator directly; avoid calling strlen first, which would waste an extra O(n) pass.