medium Problem 7 Remove All Adjacent Duplicates In String

Problem Statement

Give a string s, convert it into a valid string. A string is considered valid if it does not have any two adjacent duplicate characters.

To make a string valid, we will perform a duplicate removal process. 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.

Examples

Example 1

• Input: "abbaca"
• Expected Output: "ca"
• Description: We remove 'b' from "abbaca" to get "aaca", then remove 'a' from "aaca" to get "ca"

Example 2

• Input: "azxxzy"
• Expected Output: "ay"
• Description: We remove 'x' from "azxxzy" to get "azzy", then remove 'z' from "azzy" to get "ay"

Example 3

• Input: "abba"
• Expected Output: ""
• Description: We remove 'b' from "abba" to get "aa", then remove 'a' from "aa" to get an empty string

Constraints:

• 1 <= str.length <= 10⁵
• str consists of lowercase English letters.

Solution

To solve this problem, we can utilize a stack data structure. The stack helps us to keep track of the characters in the string as we iterate through it. For each character in the string, we compare it with the top element of the stack. If they match, it indicates a pair of adjacent duplicates, and we remove the top element from the stack. Otherwise, we add the current character to the stack. This approach effectively removes all adjacent duplicate pairs.

Once we have processed all characters, the remaining elements in the stack represent the string with all adjacent duplicates removed. The final step involves converting the stack contents back into a string in the original order, which can be achieved by reversing the stack.

Detailed Step-by-Step Walkthrough

1. Initialize an empty stack
2. Iterate over each character in the input string
3. For each character, check if the stack is not empty and the top of the stack is equal to the current character
   • If it is, pop the top element from the stack
   • If it's not, push the current character into the stack
4. After the iteration, convert the stack into a string by joining all elements in the revese order.
5. Return the final valid string.

Algorithm Walkthrough

1. Initialize an Empty Stack: Start with an empty stack to keep track of the characters.

2. Process First Character ('a'):

   • Current Character: 'a'
   • Since the stack is empty, push 'a' onto the stack.
   • Stack after operation: ['a']

3. Process Second Character ('b'):

   • Current Character: 'b'
   • 'b' is not the same as the top element of the stack ('a'), so push 'b'.
   • Stack after operation: ['a', 'b']

4. Process Third Character ('b'):

   • Current Character: 'b'
   • 'b' matches the top element of the stack, so pop the top element ('b').
   • Stack after operation: ['a']

5. Process Fourth Character ('a'):

   • Current Character: 'a'
   • 'a' matches the top element of the stack, so pop the top element ('a').
   • Stack after operation: []

6. Process Fifth Character ('c'):

   • Current Character: 'c'
   • Stack is empty, so push 'c'.
   • Stack after operation: ['c']

7. Process Sixth Character ('a'):

   • Current Character: 'a'
   • 'a' is not the same as the top element of the stack ('c'), so push 'a'.
   • Stack after operation: ['c', 'a']

8. Final Step - Convert Stack to String:

   • The resulting string is "ca".

So, the output for the input string "abbaca" is "ca", as all adjacent duplicates have been successfully removed.

Code

Here is the code for this algorithm:

import java.util.Stack;

class Solution {

  // Function to remove consecutive duplicates from a string
  public String removeDuplicates(String s) {
    Stack<Character> stack = new Stack<>(); // Create a stack to store characters
    for (char c : s.toCharArray()) {
      if (!stack.isEmpty() && stack.peek() == c) {
        // Check if the stack is not empty and the top element equals the current character
        stack.pop(); // If there's a duplicate, pop the top element from the stack
      } else {
        stack.push(c); // If the current character is not a duplicate, push it onto the stack
      }
    }

    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
      result.append(stack.pop());
    }
    return result.reverse().toString();
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.removeDuplicates("abbaca")); // Output: "ca"
    System.out.println(sol.removeDuplicates("azxxzy")); // Output: "ay"
    System.out.println(sol.removeDuplicates("abba")); // Output: ""
  }
}

Complexity Analysis

Time Complexity

• Processing the input string: The algorithm iterates through each character in the string exactly once. Each character is either pushed onto or popped from the stack, which are constant-time operations, . Therefore, iterating over the string takes , where N is the length of the input string s.

• Building the result string: Converting stack into the string takes time.

Overall time complexity: , where N is the length of the input string.

Space Complexity

• Stack space: The stack stores the characters from the input string. In the worst case (when no characters are removed), the stack will contain all characters, requiring space.

• Result string space: The result string is used to store the final result which also takes space, as it holds the result of the same size as the input string (in the worst case).

Overall space complexity: .

🎯 STRICT STANDOUT — Solution Remove Adjacent Duplicates

1. Why / judgment

If top==cur pop else push. Final stack is answer (bottom→top). StringBuilder is a fine stack. Cascades emerge from LIFO.

2. Worked complexity / trace (K11)

"abbaca": [a]→[a,b]→[a]→[]→[c]→[c,a] → "ca". "azxxzy" → "ay".
Each char once → Θ(n) time/space.

3. Pattern + when-NOT (K12)

Name: ADJACENT CANCEL STACK

Recognition: pair deletion until fixed point.

When-NOT: Sorting wrong. Queue FIFO would not cancel latest. Regex loops risk quadratic. k=2 only here (1209 generalizes).

4. Edge hand-run (K13)

"aa" → "". "abccba" → "" (cascade). "abc" → "abc".

5. Interviewer follow-ups

Q1. Cascade correctness?
A: After pop, new top may match later chars — stack handles naturally.

Q2. Naive rebuild time?
A: Repeated full scans can be O(n²).

Q3. When-not mono NGE?
A: This is equality cancel, not order-neighbor.