C++で原点から最も遠い位置を求めるアルゴリズム

問題の概要

「L」「R」「?」のいずれかの文字で構成される文字列 s があるとします。「L」は左へ1単位移動すること、「R」は右へ1単位移動することを意味し、「?」は「L」または「R」のどちらにでも置き換え可能な文字です。初期位置が0であるとき、「?」を適切に置き換えることで、原点から到達できる最大距離を求めます。

例えば、入力が "LLRRL??" の場合、出力は 3 となります。「?」をすべて「L」に置き換えると、左へ5単位、右へ2単位移動することになり、最大変位は 5 − 2 = 3 だからです。

解法のアプローチ

この問題は、次の手順で効率的に解くことができます。

• カウンタ op（「?」の個数）、l（「L」の個数）、r（「R」の個数）をそれぞれ0で初期化する

• 文字列 s 内の各文字 it に対して以下を繰り返す：

  • it が 'L' と等しい場合 → l を1増やす

  • it が 'R' と等しい場合 → r を1増やす

  • それ以外の場合（'?' の場合）→ op を1増やす

• max(l, r) − min(l, r) + op を返す

この式が正しい理由はシンプルです。「?」はすべて同じ方向に割り当てられるため、左右の確定した移動量の差（絶対値）に「?」の総数を加えれば、理論上の最大距離が得られます。つまり、既存の「L」と「R」の差がどちら向きであっても、「?」をすべて有利な側に振ることで距離を最大化できます。

実装例

以下はC++による実装コードです。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s) {
      int op = 0;
      int l = 0;
      int r = 0;
      for (auto &it : s) {
         if (it == 'L') {
            l++;
         } else if (it == 'R') {
            r++;
         } else {
            op++;
         }
      }
      return max(l, r) - min(l, r) + op;
   }
};
main() {
   Solution ob;
   cout << (ob.solve("LLRRL??"));
}

入力

"LLRRL??"

出力

3

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、補助的な記憶領域は O(1) で済みます。非常にシンプルながら、あらゆる入力長に対して高速に動作するのが特徴です。