Remove all adjacent duplicates in string

Remove All Adjacent Duplicates In String

Link

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”

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.

Implementation:

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.