JavaScriptで隣接する文字が重複しないようにするための最小削除文字数を求める方法

問題

A・B・C の3種類の文字のみで構成された文字列を受け取る JavaScript 関数を作成する必要があります。この関数の目的は、隣接するどの2文字も必ず異なる状態にするために、文字列から削除する必要がある文字の最小数を求めることです。

アプローチ

この問題は、文字列を先頭から順に走査し、隣接する2文字が同じであれば1文字を削除するというシンプルな方法で解決できます。具体的な手順は以下のとおりです。

• 文字列を split() メソッドで1文字ずつの配列に変換します。
• 配列を先頭から順に走査し、現在の文字と次の文字が一致した場合は、削除カウントを1増やしてその文字を配列から取り除きます。
• splice() による削除でインデックスがずれるため、インデックスを1つ戻して再度比較します。
• 最後に削除した文字の合計数を返します。

コード例

以下が実際のコードです。

const str = "ABBABCCABAA";
const removeLetters = (str = '') => {
   const arr = str.split('')
   let count = 0
   for (let i = 0; i < arr.length; i++) {
      if (arr[i] === arr[i + 1]) {
         count += 1
         arr.splice(i, 1)
         i -= 1
      }
   }
   return count
}
console.log(removeLetters(str));

出力

3

コードの解説

入力文字列 "ABBABCCABAA" の場合、隣接して並んでいる同じ文字のペアは「BB」「CC」「AA」の3箇所に存在します。各ペアから1文字ずつ削除すれば隣接文字がすべて異なる状態になるため、答えは 3 となります。

より効率的な書き方

実は、削除すべき文字数は「元の文字列内で隣接する同じ文字のペアの数」と一致します。そのため、配列の操作（splice）を実際に行わず、単純に隣接ペアを数えるだけで O(n) の計算量で求められます。

const removeLetters = (str = '') => {
   let count = 0;
   for (let i = 0; i < str.length - 1; i++) {
      if (str[i] === str[i + 1]) {
         count += 1;
      }
   }
   return count;
}
console.log(removeLetters("ABBABCCABAA")); // 3

どちらの方法でも同じ結果が得られますが、文字列が長い場合は後者のアプローチの方がパフォーマンスに優れています。