# Remove all adjacent duplicates in string

Companies:

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”

Note:

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

### Solution:

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.

### Java:

``````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 {
sb.append(character);
sbLength++;
}
}
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"]