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 is guaranteed that the answer is unique.

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" -> "bb" is removed -> You get "aaca" -> "aa" is removed -> You get "ca".

Example 2:

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

Clarifying Questions

1. Can the input string be empty or a single character?
   • Yes, in such cases, the result should be the string itself.
2. Are characters always lowercase English letters?
   • Yes, as per the problem statement, the string s contains only lowercase English letters.
3. Is there any limit on the length of the string?
   • There’s no explicit limit provided, so we should handle typical constraints of string length in competitive programming — usually up to (10^4) characters.

Strategy

The approach is to use a stack to aid in removing the adjacent duplicates:

1. Traverse the string character by character.
2. Push each character onto the stack if the stack is empty or the top character of the stack is not equal to the current character.
3. If the top character of the stack is equal to the current character, pop the stack (remove the duplicate pair).
4. After traversing the string, the remaining characters in the stack represent the final string without adjacent duplicates.
5. Convert the stack back into a string and return it.

Code

Here is the Java code for the solution:

import java.util.Stack;

public class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char ch : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == ch) {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        
        // Convert stack to string
        StringBuilder result = new StringBuilder();
        for (char ch : stack) {
            result.append(ch);
        }
        
        return result.toString();
    }
}

Time Complexity

• Time Complexity: (O(n)), where (n) is the length of the input string. We iterate through each character exactly once and each stack operation (push/pop) is (O(1)).
• Space Complexity: (O(n)), in the worst case, where all characters in the string are stored in the stack and no duplicates are found.

Using a stack allows us to efficiently handle the problem by keeping track of characters and easily removing adjacent duplicates as we traverse the string.

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?