1047.remove-all-adjacent-duplicates-in-string.md

1047. Remove All Adjacent Duplicates In String

Stack

We can use stack to remove adjacent duplicates. If the top of the stack is the same as the current character, we pop the top of the stack. Otherwise, we push the current character to the stack.

fun removeDuplicates(s: String): String {
    val stack = Stack<Char>()
    for (i in 0 until s.length) {
        if (!stack.isEmpty() && stack.peek() == s[i]) {
            stack.pop()
        } else {
            stack.push(s[i])
        }
    }
    return stack.joinToString("")
}

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(n).

Two Pointers

We have read and write pointers. The read pointer reads the characters from the string. The write pointer is the next index to write the character. If the current character is the same as the previous character, we decrease the write pointer. Otherwise, we write the current character to the write pointer.

For example, the read point is at index 2, s[read] == s[write - 1] which is adjacent duplicate, so we decrease the write pointer.

  0 1 2 3 4 5
  a b b a c a
      r
      w

// After
  0 1 2 3 4 5
  a b b a c a
      r
    w

// At the end of iteration
  0 1 2 3 4 5
  c a b a c a // We have overwritten the string at index 0 and 1.
              r
      w 

// Return the substring from 0 to write pointer
  0 1 2 3 4 5
  c a
               r
      w

fun removeDuplicates(s: String): String {
    val c = s.toCharArray()
    val n = s.length
    var read = 1
    var write = 1
    while (read < n) {
        if (write - 1 >= 0 && c[read] == c[write - 1]) {
            write--
        } else {
            c[write] = c[read]
            write++
        }
        read++
    }
    return c.concatToString(0, write)
}

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(n) for converting the string to char array.