algoadvance

Given a string s, 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 can be proven that the answer is unique.

Example:

1. Input: s = "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 resulting string is “aaca”, of which only “aa” are possible moves.
   • Finally, we remove “aa” to obtain “ca”.

Clarifying Questions:

1. Can the input string contain non-alphabetic characters?
   • For this problem, assume the string only contains lowercase English letters.
2. What should be returned if the input string is empty?
   • An empty string should be returned.

Strategy:

1. Using a Stack:
   • Use a stack to process the string. Traverse through each character in the string.
   • For each character:
     • If the stack is not empty and the top of the stack is the same as the current character, pop the top of the stack (i.e., remove the adjacent duplicates).
     • Otherwise, push the current character onto the stack.
   • After processing all characters, the stack will contain the resulting string with no adjacent duplicates.
2. Return the string formed by the characters in the stack.

Code:

def removeDuplicates(s: str) -> str:
    stack = []
    
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    
    return ''.join(stack)

# Example usage
s = "abbaca"
print(removeDuplicates(s))  # Output: "ca"

Time Complexity:

• O(n): We traverse the string only once where n is the length of the string s.
  • Each element is pushed and popped from the stack at most once.

Space Complexity:

• O(n) in the worst case where none of the characters are adjacent duplicates, resulting in all characters being pushed on the stack.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?