Remove All Adjacent Duplicates In String

Problem Statement

In this problem, you are provided a string s consisting solely of lowercase English letters. The core operation you can perform on this string is termed a duplicate removal. This operation involves identifying and removing two consecutive, identical letters from the string. You are required to apply this operation repeatedly until no further duplicate removals are possible. The goal is to determine and return the final configuration of the string after all possible duplicate removals have been executed. Importantly, it is guaranteed that the resulting string after all operations is unique, making the problem deterministic in nature.

Examples

Example 1

Input:

s = "abbaca"

Output:

"ca"

Explanation:

For 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

Input:

s = "azxxzy"

Output:

"ay"

Constraints

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Approach and Intuition

Understanding the sequential nature of operations and relying on incremental removals holds the key to efficiently solving this problem. Using a stack-based approach provides a direct and effective solution:

1. Initialize an empty stack to support the removal operations.

   • This stack will help in efficiently executing the repeated removal of duplicate characters.

2. Iterate through each character in the input string:

   • If the stack is not empty and the top of the stack contains the same character as the current character from the string, this indicates the presence of a duplicative pair.
   • In such cases, pop the top character of the stack (i.e., remove this pair of duplicates from further consideration).
   • If the stack is empty or the top character of the stack is different from the current character, push the current character onto the stack. This action effectively delays the decision of duplicate removal till a matching character appears.

3. During this traversal, the stack evolves only to contain characters that couldn't yet find a match for removal.

4. After iterating through all characters, the remaining content of the stack presents the reduced string post all possible duplicate removals.

With this approach, each character in the string is processed exactly once for pushing and at most once for popping, making the solution remarkably efficient with a time complexity of O(n), where n is the length of the string. This operating efficiency, coupled with the stack’s inherent nature of Last-In-First-Out (LIFO), positions it as the optimal tool for addressing pairs of characters as they appear in sequence.

Solutions

class Solution {
  public String deleteRepeatedChars(String str) {
    StringBuilder result = new StringBuilder();
    int lengthResult = 0;
    for(char c : str.toCharArray()) {
      if (lengthResult != 0 && c == result.charAt(lengthResult - 1))
        result.deleteCharAt(lengthResult-- - 1);
      else {
        result.append(c);
        lengthResult++;
      }
    }
    return result.toString();
  }
}