【JavaScript】文字列に含まれる最長の同一文字連続(文字列の「力」)を求める方法

文字列の「力」とは?

文字列の「力(power)」とは、たった1種類の文字だけで構成された、空でない部分文字列のうち最も長いものの長さとして定義されます。

つまり今回の課題は、任意の文字列を引数として受け取り、その文字列の力を返すJavaScript関数を実装することです。

例

たとえば、次のような文字列を考えてみましょう。

const str = "abbcccddddeeeeedcba"

この場合、期待される出力は 5 になります。

その理由は、文字 'e' だけで構成された部分文字列 "eeeee" の長さがちょうど5であり、条件を満たす部分文字列の中でこれが最も長いためです。

サンプルコード

この問題は、文字列を先頭から一度走査しながら「同じ文字が何文字連続しているか」を数えることで解けます。実装例は以下のとおりです。

const str = "abbcccddddeeeeedcba";

const maxPower = (str = '') => {
  let power = 1;  // 結果(1文字以上なら最小でも1)
  let count = 1;  // 現在の連続文字数
  
  for (let i = 1; i < str.length; i++) {
    if (str[i] === str[i - 1]) {
      count++;  // 直前の文字と同じ → 連続数を増やす
      power = Math.max(power, count);  // 最大値を更新
    } else {
      count = 1;  // 文字が変わったらカウントをリセット
    }
  }
  
  return power;
};

console.log(maxPower(str));

コードの仕組み

アルゴリズムの流れを整理すると、次のようになっています。

• 変数 power(最終的な答え)と count(現在の連続文字数)を、どちらも 1 で初期化します。文字列が1文字以上であれば、力は最低でも1になるためです。
• 文字列を2文字目から順に走査し、現在の文字が直前の文字と一致しているかどうかを判定します。
• 一致している場合は count を1増やし、Math.max() によって power をより大きな値へ更新します。
• 異なる文字に切り替わった場合は、count を1に戻して新しい連続のカウントを開始します。
• 走査が終わった時点の power が、まさに求める「文字列の力」です。

なお、空文字列が渡された場合もループは実行されず 1 が返ります。「力」は必ず1文字以上の部分文字列を対象とするため、実運用では入力チェックを加えてもよいでしょう。

計算量

文字列全体を一度だけ走査するため、時間計算量は O(n)。使用するのは固定個の変数のみなので、空間計算量は O(1) で済みます。非常に長い文字列に対しても高速に動作する効率的なアプローチです。

実行結果

コンソールには次のように出力されます。

5