JavaScriptで文字列の最小削除回数を求める方法

問題の概要

例えば、次のようなバイナリ文字列（「0」と「1」だけで構成された文字列）があるとします。

const str = '001001';

私たちの課題は、このような文字列を唯一の引数として受け取るJavaScript関数を作成することです。

関数の役割は、入力された文字列に対して隣り合う2つの文字が同じにならないようにするために必要な最小削除回数を計算し、その結果を返すことです。

例えば、上記の文字列の場合、出力は次のようになります。

const output = 2;

これは、インデックス0と3にある「0」を削除すると、新しい文字列が「0101」となり、隣接する文字がすべて異なる最長の文字列になるためです。

アルゴリズムの考え方

この問題は実はとてもシンプルに解くことができます。ポイントは次のとおりです。

• 隣り合う文字が同じペア（例：「00」「11」）を見つけるたびに、そのうち1文字を削除すればよい。
• したがって、「隣接する同一文字ペアの出現回数」を数え上げれば、それがそのまま最小削除回数となる。

コード例

const str = '001001';
const minimumDeletions = (str = '') => {
   let count = 0;
   const { length } = str;
   for(let i = 0; i < length; i++){
      if (str[i] === str[i + 1]){
         count++;
      };
   }
   return count;
};
console.log(minimumDeletions(str));

コードの解説

このコードでは、文字列を先頭から順に走査し、現在の文字 str[i] と次の文字 str[i + 1] を比較しています。両者が一致していた場合はカウントを1増やします。ループが終了した時点での count の値が、求めるべき最小削除回数になります。計算量はO(n)で、文字列の長さに比例して一度だけ走査すればよいため、非常に効率的です。

出力結果

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

2