JavaScriptで解く「表現豊かな単語」問題：文字列の伸縮判定アルゴリズム

人は感情を強調するために、同じ文字を繰り返して使うことがあります。例えば「hello」→「heeellooo」、「hi」→「hiiii」のような変換です。「heeellooo」のような文字列には、「h」「eee」「ll」「ooo」といった、同じ文字が連続して並ぶグループが存在します。

ある文字列 S に対して、クエリとなる単語が「伸縮可能（stretchy）」であるとは、次の拡張操作を何度か適用することで、その単語を S と一致させられることを意味します。

拡張操作： 文字 c からなるグループを選び、そこに文字 c を追加して、グループのサイズを 3 以上にする。

例えば、「hello」からスタートして、グループ「o」に拡張操作を行えば「hellooo」を作れますが、「helloo」は作れません。グループ「oo」のサイズが 3 未満だからです。さらに「ll」→「lllll」という拡張を加えれば「helllllooo」も作れます。つまり S = "helllllooo" の場合、クエリ単語「hello」は次のように 2 回の拡張で S に到達できるため、伸縮可能ということになります。

query = "hello" → "hellooo" → "helllllooo" = S

この問題では、クエリ単語のリストが与えられたとき、その中で伸縮可能な単語の個数を返す必要があります。

入出力の例

入力文字列が次の場合：

const str = 'heeellooo';

単語のリストが次の場合：

const words = ["hello", "hi", "helo"];

期待される出力は次の通りです。

const output = 1;

この結果になる理由を見てみましょう。「hello」は拡張操作によって「heeellooo」に一致させられるので伸縮可能ですが、「hi」と「helo」はどのような拡張を行っても一致させられないため、該当数は 1 となります。

解法のコード

この問題は2 ポインタ（two pointers）を使うことで効率的に解けます。基準文字列 str と各クエリ単語 w を先頭から同時に走査し、対応する位置の文字が同じか、そしてそれぞれの文字グループの長さが条件を満たすかを順番に確認していきます。

const str = 'heeellooo';
const words = ["hello", "hi", "helo"];

const extraWords = (str, words) => {
   let count = 0;
   // 各クエリ単語について判定を行う
   for (let w of words) {
      let i = 0; // str の走査用ポインタ
      let j = 0; // 単語 w の走査用ポインタ

      // 先頭から文字ごとに比較を進める
      for (; i < str.length && j < w.length && w[j] === str[i];) {
         let lenS = 1; // str 側の同一文字グループの長さ
         let lenW = 1; // 単語側の同一文字グループの長さ

         // str 側のグループ長を測定
         for (; i + lenS < str.length && str[i + lenS] === str[i]; lenS++);
         // 単語側のグループ長を測定
         for (; j + lenW < w.length && w[j + lenW] === w[j]; lenW++);

         // 単語側のグループが長すぎる場合、
         // または str 側が 3 未満で長さが異なる場合は不成立
         if (lenS < lenW || lenS > lenW && lenS < 3) break;

         i += lenS;
         j += lenW;
      }

      // 両方の文字列を最後まで走査できれば伸縮可能
      if (i === str.length && j === w.length) {
         count++;
      }
   }
   return count;
};

console.log(extraWords(str, words));

実行結果

コンソールに出力される結果は次の通りです。

1

アルゴリズムのポイント

• 時間計算量： 各単語の判定は O(N)（N は文字列の長さ）で行えるため、全体でも非常に高速です。
• 判定条件： グループ長の関係は「単語側 ≤ 基準側」かつ「基準側のグループが 3 以上または両者が等しい」場合のみ成立します。
• 終了条件： 両方のポインタがそれぞれの文字列末尾に到達したときのみ、その単語をカウントします。

このように、文字列をグループ単位で比較するアプローチを取ることで、無駄な組み合わせ探索を避けながら正確に伸縮可能な単語を判定できます。