【初心者向け】JavaScriptで文字列から隣接する重複文字を削除する方法

問題

文字列 str を唯一の引数として受け取る JavaScript 関数を作成します。

ここでいう「重複の削除」とは、隣接する2つの同じ文字を選び、それらを取り除く操作を指します。

この操作を文字列 str に対して繰り返し実行し、それ以上削除できる箇所がなくなるまで続けます。

最終的に、すべての重複削除が完了した後の文字列を関数から返します。

たとえば、関数への入力が以下だった場合：

const str = 'kllkmk';

出力は次のようになります：

const output = 'mk';

出力の解説

まず文字列から「ll」を削除して「kkmk」にし、続けて「kk」を削除することで、最終的な文字列「mk」が得られます。

解決策：スタックを使ったアプローチ

この問題は、スタック（配列）を活用することで効率的に解けます。文字列を先頭から1文字ずつ走査し、スタックの末尾にある文字と一致した場合は取り除き（pop）、一致しない場合は追加する（push）というシンプルなルールで処理を進めます。

サンプルコード

const str = 'kllkmk';
const removeDuplicates = (str = '') => {
    const arr = [];
    for(const char of str){
        if(char === arr[arr.length - 1]){
            while(arr[arr.length - 1] === char){
                arr.pop();
            };
        } else {
            arr.push(char);
        };
    };
    return arr.join('');  
};
console.log(removeDuplicates(str));

コードの解説

• 配列 arr をスタックとして使用： 処理済みの文字を一時的に保持します。
• 現在の文字がスタック末尾と一致する場合： while ループで一致する限り pop() を呼び出し、隣接する重複をまとめて削除します。
• 一致しない場合： push() で現在の文字をスタックに追加します。
• 最後に join('') で連結： 残った文字をつなげて、結果の文字列として返します。

このアプローチにより、各文字は一度だけ push / pop の対象となるため、時間計算量は O(n) となり、非常に効率的です。

出力

コンソールには次のように表示されます：

mk