easy Remove All Adjacent Duplicates In String

Problem Statement

You are given a string s consisting of lowercase English 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.

Examples

1. • Input: s = "abccba"
   • Output: ""
   • Explanation: First, we remove "cc" to get "abba". Then, we remove "bb" to get "aa". Finally, we remove "aa" to get an empty string.
2. • Input: s = "foobar"
   • Output: "fbar"
   • Explanation: We remove "oo" to get "fbar".
3. • Input: s = "fooobar"
   • Output: "fobar"
   • Explanation: We remove the pair "oo" to get "fobar".
4. • Input: s = "abcd"
   • Output: "abcd"
   • Explanation: No adjacent duplicates so no changes.

Constraints:

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

Solution

This problem can be solved efficiently using a stack, which can mimic the process of eliminating adjacent duplicates.

Algorithm Walkthrough

1. Initialize an empty stack.
2. Loop through the characters in the given string s.
3. For each character:
   • If the stack is not empty and the current character is the same as the top character on the stack, pop the character from the stack.
   • Otherwise, push the current character onto the stack.
4. Finally, build the result string from the characters remaining on the stack.

Code

Here is the code for this algorithm:

import java.util.Stack;

public class Solution {

  public String removeDuplicates(String s) {
    // Initialize stack
    Stack<Character> stack = new Stack<>();

    // Process each character in s
    for (char c : s.toCharArray()) {
      // If the stack is not empty and the current character is the same as the top of the stack, pop the character from the stack
      if (!stack.isEmpty() && c == stack.peek()) {
        stack.pop();
      } else { // Push the current character onto the stack
        stack.push(c);
      }
    }

    // Join the stack to a string
    StringBuilder result = new StringBuilder();
    for (Character c : stack) {
      result.append(c);
    }
    return result.toString();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.removeDuplicates("abccba")); // Output: ""
    System.out.println(solution.removeDuplicates("foobar")); // Output: "fbar"
    System.out.println(solution.removeDuplicates("abcd")); // Output: "abcd"
  }
}

Time and Space Complexity

The time complexity of this algorithm is , where N is the length of s, because we perform one operation per character in s. The space complexity is also , as in the worst case, every character in s is pushed onto the stack.