今日のアルゴリズム: 文字列内の隣接する重複をすべて削除する

[[419471]]

小文字で構成される文字列 S が与えられた場合、重複削除操作は隣接する 2 つの同一文字を選択して削除します。

重複排除操作は、重複排除が実行できなくなるまで S 上で繰り返し実行されます。

すべての重複削除操作が完了した後の最終文字列を返します。答えは必ず一意になります。

例：

入力: 「abbaca」  
出力: "ca"  
説明する：
たとえば、 「abbaca」では、2 つの文字が隣接していて同じであるため、 「bb」を削除できます。これは、現時点で削除できる唯一の重複です。すると、文字列「aaca」が取得されますが、そのうち「aa」のみが重複排除できるため、最終的な文字列は「ca」になります。

ヒント：

1. <= 長さ <= 20000
2. S は小文字の英語のみで構成されます。

解決策: スタックの使用

解決方法: 文字列をトラバースし、1 つずつスタックにプッシュします。スタックにプッシュするときに、スタックの先頭要素と一致しているかどうかを判断します。一致している場合、つまり 2 つの要素が同じで隣接している場合は、スタックの先頭要素をポップアウトする必要があり、現在の要素をスタックにプッシュする必要はありません。

解決手順: 文字列を走査し、スタックの先頭文字を取り出し、現在の文字がスタックの先頭文字と一致しているかどうかを判断します。

• 矛盾しており、先頭の文字がスタックにプッシュされ、現在の文字がスタックにプッシュされます
• スタック ヘッド文字は現在の文字と同じであり、それに隣接しています。どちらの文字もスタックにプッシュする必要はなく、次のトラバーサルを直接実行できます。

トラバーサルが完了したら、スタック内の文字列を返します。

コード実装:

 const removeDuplicates =関数(S) {
    スタック = []
 (c of S)の場合{
        prev = stack.pop() とします。
        if(前 !== c) {
            スタック.push(前)
            スタックをプッシュする(c)
        }
    }
スタックの結合( ' ' )を返す
};

• 時間計算量: O(n)
• 空間計算量: O(n