Remove all adjacent duplicates in string

  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Oracle Interview Questions


Companies: Bloomberg, Facebook, Google, Oracle

Given a string S of lowercase 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. It is guaranteed the answer is unique.

Example 1:

Input: S = “xyyz”

Output: S = “xz”

Example 2:

Input: S = “ababbac”

Output: S = “abc”


  • 1 <= S.length <= 20000
  • S consists only of English lowercase letters.


Suppose we take a stack and push first character in the stack. Through stack we can easily perform this operations:

  • If the current character is equal to the top of the stack, perform pop operation.
  • If the current character is not equal to the top of the stack, push operation is performed.

We can implement the stack using StringBuilder in java and list in python.



class Solution {
  public String removeDuplicates(String S) {
    StringBuilder sb = new StringBuilder();
    int sbLength = 0;
    for(char character : S.toCharArray()) {
      if (sbLength != 0 && character == sb.charAt(sbLength - 1))
        sb.deleteCharAt(sbLength-- - 1);
      else {
    return sb.toString();

Complexity Analysis:

  • Time Complexity: O(N), N is the string length.
  • Space Complexity: O(N-D), D is total length for all duplicated.

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]