algoadvance

Leetcode 1047. Remove All Adjacent Duplicates In String

Problem Statement

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"

2. Input: s = "azxxzy" Output: "ay"

Constraints

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

Clarifying Questions

Before proceeding, let’s ensure we understand the problem thoroughly:

1. Do all the removals need to happen in a single pass or can they be sequenced iteratively?
   • We perform removals iteratively until no adjacent duplicates are left.
2. Should the output string be the smallest lexicographically?
   • No, the task just requires removing adjacent duplicates iteratively until the string can no longer be reduced.
3. Can the input string start or end with duplicates?
   • Yes, the input string can have duplicates in any position.

Strategy

1. Using Stack:
   • We can use a stack to store characters and check for duplicates:
     • Traverse each character in the string.
     • If the stack is not empty and the top character of the stack is the same as the current character, we pop from the stack (removing the duplicate).
     • Otherwise, we push the current character onto the stack.
   • Convert the stack to a string, which will be our resultant string after removing all adjacent duplicates.

Why Stack?

• A stack allows us to keep track of characters and to efficiently remove duplicates in an iterative manner. By using the stack, each character is visited at most twice (once when added and once when removed), guaranteeing linear time complexity.

Time Complexity

• O(n) where n is the length of the string s because each character is pushed onto and popped from the stack at most once.

Code

#include <iostream>
#include <stack>
#include <string>

std::string removeDuplicates(std::string s) {
    std::stack<char> charStack;
    
    for (char c : s) {
        // If stack is not empty and top element is same as current char, pop the stack
        if (!charStack.empty() && charStack.top() == c) {
            charStack.pop();
        } else {
            charStack.push(c);
        }
    }
    
    // Construct the result string from the stack
    std::string result = "";
    while (!charStack.empty()) {
        result = charStack.top() + result;
        charStack.pop();
    }
    
    return result;
}

// Example usage
int main() {
    std::string s = "abbaca";
    std::cout << "Result: " << removeDuplicates(s) << std::endl;
    
    s = "azxxzy";
    std::cout << "Result: " << removeDuplicates(s) << std::endl;

    return 0;
}

This code correctly handles duplicate removals iteratively and outputs the resulting string when no more adjacent duplicates exist.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?