Remove All Adjacent Duplicates In String

Problem Description

Ah, the classic problem of removing adjacent duplicates from a string! It’s like trying to clean up your messy room, only to find that every time you put something away, another item mysteriously duplicates itself. You know, like that one sock that always seems to multiply in the laundry basket.

In this problem, you are given a string S, and your task is to remove all adjacent duplicates. If two characters are the same and next to each other, they should be removed. This process continues until no more adjacent duplicates exist.

For example, if you have the string “abbaca”, you should end up with “ca”. Why? Because the “bb” and “aa” are adjacent duplicates that need to be sent packing!

Code Solution


class Solution {
  public String removeDuplicates(final String S) {
    StringBuilder sb = new StringBuilder();

    for (final char c : S.toCharArray()) {
      final int n = sb.length();
      if (n > 0 && sb.charAt(n - 1) == c)
        sb.deleteCharAt(n - 1);
      else
        sb.append(c);
    }

    return sb.toString();
  }
}

Approach

The approach here is quite straightforward. We utilize a StringBuilder to build our result string. As we iterate through each character in the input string, we check if the last character in our StringBuilder is the same as the current character. If it is, we remove the last character (because, you know, they’re duplicates). If not, we simply append the current character to our StringBuilder. This continues until we’ve processed all characters in the string.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the string. We traverse the string once.
Space Complexity	O(n) in the worst case, where no duplicates are present, and we store all characters in the `StringBuilder`.

Real-World Example

Imagine you’re at a party, and you keep running into the same people over and over again. You’d probably want to avoid those awkward encounters, right? This problem is like that! You want to eliminate those repetitive interactions (or characters) so you can enjoy the party (or string) without the duplicates ruining your fun.