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.
Solution:
class Solution:
def removeDuplicates(self, S: str) -> str:
stack = []
for x in S:
if len(stack) >= 1 and x == stack[-1]:
stack.pop()
else:
stack.append(x)
return "".join(stack)
Explanation:
Instead of thinking of how to remove those adjacent and duplicate elements in the original string, we should try to build a new list from the beginning. The main idea here is to initialize a list and append elements from S. At the meanwhile, we need to always compare the current element and the last element appended. If they are the same, we don't append the new element and pop the last one, else we append the current to the list. When the stack has no element left, we don't need to compare and thus can add the new element directly.
