Remove All Adjacent Duplicates In String [LeetCode 1047]

https://leetcode.com/contest/weekly-contest-137/problems/remove-all-adjacent-duplicates-in-string/

文字列Sが与えられる。
隣り合う文字が等しければその2文字を消すという操作をできなくなるまで行う。
最終的にできる文字列はどうなるか。
なお、最終的にできる文字列は一意に定まる。

1 ≦ Sの長さ ≦ 20000

解説

https://leetcode.com/contest/weekly-contest-137/submissions/detail/229841627/

最終的にできる文字列は一意に定まるらしいので、どういう順番で消すかはあまり考えなくていい。
なので、先頭から見ていって消す操作が行えれば消すというのを繰り返していくシミュレーションで解く。
文字列が結構長いので、愚直にやって間に合うか心配だが、2文字ずつ減っていくというのと、
順位表を見ると、爆速かつペナ無しで通している人が多いので、やったれで投げると通る。

class Solution {
public:
	string removeDuplicates(string S) {
		int n = S.length();

		rep(i, 0, n - 1) if (S[i] == S[i + 1]) {
			string nxt = "";
			if (0 < i) nxt = S.substr(0, i);
			if (i + 2 < n) nxt += S.substr(i + 2);
			return removeDuplicates(nxt);
		}

		return S;
	}
};