Solution: Remove All Adjacent Duplicates In String

Let's solve the Remove All Adjacent Duplicates In String problem using the Stacks pattern.

We'll cover the following

Statement

You are given a string consisting of lowercase English letters. Repeatedly remove adjacent duplicate letters, one pair at a time. Both members of a pair of adjacent duplicate letters need to be removed.

Constraints:

  • 1≤1 \leq string.length ≤103\leq 10^3
  • string consists of lowercase English alphabets.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to generate a set of all possible adjacent duplicates in a string of small English alphabets, that is, {"aa", "bb", "cc", "dd", ...}. Traverse over the string to see if such duplicates are present. We’ll use nested loops to check this condition. If duplicate characters are found, we’ll remove the adjacent duplicates from the input string. For example, in the "abaac" string, we’ll remove "aa" from the string, which results in "abc".

Since we’re using nested loops, the time complexity of this approach is O(n2)O(n^2), which is not optimal. Let’s see if we can use the stacks pattern to reduce the time complexity of our solution.

Optimized approach using stacks

We can remove adjacent duplicates in pairs, which is similar to matching opening and closing parentheses. In such problems, we typically use stacks to store intermediate results to deal with nested pairs of parentheses. We’ll use the same concept here.

We’ll initialize a stack first. Then, we’ll iterate the complete string from left to right, and for every character, we’ll check the following:

  • If the stack is empty, we’ll push the character onto the stack.
  • If the stack is not empty, we’ll perform the following tasks:
    • If the string’s character is different from the stack’s top character, we’ll push the string’s character onto the stack because we did not find the adjacent duplicate.
    • If the string’s character is the same as the stack’s top character, it means that we found the adjacent duplicate characters. We’ll pop that character from the stack and move to the next character in the string.
  • After the entire string has been traversed, the remaining characters in the stack will be our result. We’ll form a string from those characters and return it.

The slides below illustrate how we’d like the algorithm to run:

Let’s look at the code for this solution:

import java.util.*;
class RemoveAdjacent {
    public static String removeDuplicates(String s) {
        Stack <Character> stack = new Stack<>();
        for (char c: s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.reverse().toString();
    }
    // Driver code
    public static void main(String[] args) {
        String[] inputs = {
            "g",
            "ggaabcdeb", 
            "abbddaccaaabcd",
            "aannkwwwkkkwna", 
            "abbabccblkklu"
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.println((i + 1) + ".\tRemove duplicates from string: '" + inputs[i] + "'");
            String resultingString = removeDuplicates(inputs[i]);
            System.out.println("\tString after removing duplicates: " + resultingString);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Remove All Adjacent Duplicates In String

Solution summary

To recap, the solution to this problem can be divided as follows:

  1. Create an empty stack to store characters.
  2. Iterate over the input string and push the character onto the stack if the stack is either empty or the stack’s top element is different from the string’s character.
  3. If they both are the same, pop an element from the stack.
  4. After the entire string has been traversed, the remaining characters in the stack represent the input string without adjacent duplicates.

Time complexity

We iterate over all the nn characters of the given string exactly once. For each character, we’ll perform O(1)O(1) operations. Therefore, the time complexity of this solution is O(n)O(n).

Space complexity

The space complexity of this solution is O(n)O(n) in the worst-case scenario when the stack stores all the characters. This will happen when each character appears exactly once in the input string.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.