https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/submissions/

Input: "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

그냥 stack으로 풀어보면

class Solution {
public:
	string removeDuplicates(string S) {
		std::stack<char> cStack;
		
		for (int i = 0; i < S.size(); ++i)
		{
			if (!cStack.empty())
			{
				if (cStack.top() != S[i])
				{
					cStack.push(S[i]);
				}
				else
				{
					cStack.pop();
				}
			}
			else
				cStack.push(S[i]);

		}
		string result;
		while (!cStack.empty())
		{
			result += cStack.top();
			cStack.pop();
		}
		std::reverse(result.begin(), result.end());
		return result;
	}
};

Runtime: 24 ms, faster than 66.74% of C++ online submissions for Remove All Adjacent Duplicates In String.

Memory Usage: 10.7 MB, less than 56.10% of C++ online submissions for Remove All Adjacent Duplicates In String.

stack의 개념으로 string을 사용해 풀어보면

class Solution {
public:
	string removeDuplicates(string S) {
		string temp;
		for (int i = 0; i < S.size(); ++i)
		{
			if (!temp.empty())
			{
				if (temp.back() != S[i])
				{
					temp.push_back(S[i]);
				}
				else
				{
					temp.pop_back();
				}
			}
			else
				temp.push_back(S[i]);

		}
		return temp;
	}
};

Runtime: 16 ms, faster than 89.93% of C++ online submissions for Remove All Adjacent Duplicates In String.

Memory Usage: 10.1 MB, less than 80.39% of C++ online submissions for Remove All Adjacent Duplicates In String.

Runtime: 12 ms, faster than 97.83% of C++ online submissions for Remove All Adjacent Duplicates In String.

Memory Usage: 10.1 MB, less than 84.49% of C++ online submissions for Remove All Adjacent Duplicates In String.

꽤 좋은 결과를 얻었다.

처음부터 끝까지 훑었으니까 O(n)의 time complexity 를 가진다.