1047. Remove All Adjacent Duplicates In String

Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made.  It is guaranteed the answer is unique.

 

Example 1:

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".
 

Note:

1 <= S.length <= 20000
S consists only of English lowercase letters.

这题是移除字符串内任意相同的两个字符。这题一开始我理解错了，以为是移除所有相同的字符，所以变复杂了。暴力破解就是每次都扫一遍，进行移除，正常来说O(N)即可解决了，这里把我想错的算法也写上来吧。

class RemoveAllAdjacentDuplicatesInString : public Solution {
public:
    void Exec() {
        cout << "Case 1: " << removeDuplicates("abbaca") << std::endl;
    }
    string removeDuplicatesAll(string S) {
        string res;
        char last_erase = 0;
        
        for (int i = 0; i < S.size(); i++) {
            if (res.empty()) {
                res.push_back(S[i]);
                last_erase = 0;
            } else if (S[i] == res.back()) {
                res.pop_back();
                last_erase = S[i];
            } else if (S[i] != last_erase) {
                res.push_back(S[i]);
                last_erase = 0;
            }
        }

        return res;
    }
    string removeDuplicates(string S) {
        string res;
        
        for (int i = 0; i < S.size(); i++) {
            if (res.empty()) {
                res.push_back(S[i]);
            } else if (S[i] == res.back()) {
                res.pop_back();
            } else {
                res.push_back(S[i]);
            }
        }

        return res;
    }
};