C++で文字列の末尾に到達するために必要な最大ジャンプ力を求める方法

このチュートリアルでは、文字列の末尾に到達するために必要な最大ジャンプ力（パワー）を求めるプログラムについて解説します。

ここで扱う問題は、0と1のみで構成された文字列が与えられ、「現在位置と同じ要素に移動できる」という条件のもとで、文字列の先頭から末尾へ移動する際に必要となる最大ジャンプ力を求めるというものです。

アルゴリズムの考え方

ポイントとなるのは、文字列の最後の文字です。移動できるのは「現在位置と同じ要素」のみなので、実質的には最後の文字と同じ文字の位置だけを踏み台として進んでいくことになります。したがって、隣り合う同じ文字同士の間隔を数え、その最大値が答えとなります。

実装例

#include<bits/stdc++.h>
using namespace std;
// 最大ジャンプ力を求める関数
int powerOfJump(string s) {
    int count = 1;
    int max_so_far = INT_MIN;
    char ch = s[s.length() - 1];
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == ch) {
            if (count > max_so_far) {
                max_so_far = count;
            }
            count = 1;
        }
        else
            count++;
    }
    return max_so_far;
}
int main(){
    string st = "1010101";
    cout<<powerOfJump(st);
}

出力

2

コードの解説

上記のコードでは、まず文字列の最後の文字を変数 ch に取得します。続いて文字列を先頭から走査し、ch と一致する文字を見つけるたびに、前回一致した位置からの距離（カウント）を記録します。この距離がこれまでの最大値 max_so_far より大きければ更新し、カウントを1に戻して次の区間の計測に備えます。

例として「1010101」という文字列を考えてみましょう。最後の文字は「1」であり、「1」の出現位置の間隔はすべて2です。そのため、実行結果として 2 が出力されます。

このアルゴリズムの計算量は文字列の長さを n とすると O(n) であり、非常に効率的です。