"""
Solution for 1047. Remove All Adjacent Duplicates In String
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/
"""

class Solution:
    """
    Runtime: 72 ms, faster than 92.32% of Python3 online submissions for Remove All Adjacent
        Duplicates In String.
    Memory Usage: 13.7 MB, less than 100.00% of Python3 online submissions for Remove All Adjacent
        Duplicates In String.
    """
    def removeDuplicates(self, S):
        """
        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".
        Args:
            S: str value to remove adjacent duplicate

        Returns:
            str: where the adjacent duplicates are removed from S
        """
        stack = []
        for char in S:
            if not stack or stack[-1] != char:
                stack.append(char)
            else:
                _ = stack.pop()

        return ''.join(stack)
