Description

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. It can be proven that the answer is unique.

Example 1:

1Input: s = "abbaca"
2Output: "ca"
3Explanation: 
4For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

1Input: s = "azxxzy"
2Output: "ay"

Constraints:

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

Solution

Naive Approach

If we think about it, we just need to iterate through input string s and whenever we find duplicates, we just have to move to next character, we basically need to skip two characters. We can use substring() method to delete few characters.

 1class Solution {
 2    public String removeDuplicates(String s) {
 3        for (int i = 1; i < s.length(); i++) {
 4            if (s.charAt(i) == s.charAt(i - 1)) {
 5                s = s.substring(0, i - 1) + s.substring(i + 1);
 6                i = 0;
 7            }
 8        }
 9        return s;
10    }
11}

There are few serious problems with this. First, it is using string modification. In Java, string is immutable and we are modifying string multiple times in each iteration when we use substring() methods. All these adds to time complexity.

Using Stack and StringBuilder

We can use Stack to insert all unique elements. When the last inserted element matches the next character, we know that we have duplicates. At this point, we pop the last element from stack and move on to next character in the string. At the end of the iteration of string, again iterate over stack elements and append to StringBuilder to create string.

 1class Solution {
 2    public String removeDuplicates (String s) {
 3        Stack<Character> stack = new Stack<>();
 4        for (char c : s.toCharArray()) {
 5            if (!stack.isEmpty() && stack.peek() == c) {
 6                stack.pop();
 7            } else {
 8                stack.push(c);
 9            }
10        }
11        StringBuilder sb = new StringBuilder();
12        for (char c : stack) {
13            sb.append(c);
14        }
15        return sb.toString();
16    }
17}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Here, we had to iterate over string and then through stack. Instead of this, if we can manipulate StringBuilder, we can avoid one iteration of stack.

Using StringBuilder

 1class Solution {
 2    public String removeDuplicates (String s) {
 3        StringBuilder sb = new StringBuilder();
 4        int stringLength = 0;
 5        for (char c: s.toCharArray()) {
 6            if (stringLength > 0 && sb.charAt(stringLength - 1) == c) {
 7                sb.delete(stringLength - 1, stringLength);
 8                stringLength--;
 9            } else {
10                sb.append(c);
11                stringLength++;
12            }
13        }
14        return sb.toString();
15    }
16}
  • Time Complexity: O(n)
  • Space Complexity: O(n)