Problem Explanation

We are asked to remove all adjacent duplicate characters from a given string S until no further removal is possible. Here, adjacent means two identical characters side by side, and duplicate simply means they are the same. The process is to be repeated until there are no more adjacent duplicates in the string.

Example

Taking a string "abbaca" as an example, we could remove "bb" first since the letters are adjacent and the same. This makes the string "aaca". Secondly we would remove "aa" which makes the string "ca". And since there are no more adjacent duplicates, we will stop and return "ca" as the final string.

Approach

The simple approach is to iterate through the string. For every character, we check if it's the same as the last character in our result string (if it is not empty). If it is, we pop the last character from our result. If it's not, we simply add the current character to the result. This can be done using a stack data structure.

Steps

• Initialize an empty answer string.
• Iterate through each character in the string.
• For each character:
  • If the answer string is not empty and the last character in the answer string is equal to the current character, then remove the last character from the answer.
  • Otherwise, add the current character to the answer.
• At the end, return the answer string.

This approach ensures that we only keep characters in the answer string that have not been removed due to adjacency duplicates.

Solution

Python

1
2python
3class Solution:
4    def removeDuplicates(self, S: str) -> str:
5        res = []
6        for c in S:
7            # if the last character is equal to the current one, pop it
8            if res and res[-1] == c:
9                res.pop()
10            # else, add the current character to the result
11            else:
12                res.append(c)
13        return ''.join(res)

Java

1
2java
3class Solution {
4    public String removeDuplicates(String S) {
5        StringBuilder ans = new StringBuilder();
6        for (char c: S.toCharArray()) {
7            int len = ans.length();
8            if (len != 0 && ans.charAt(len - 1) == c)
9                ans.deleteCharAt(len - 1);  // remove the last character
10            else
11                ans.append(c);
12        }
13        return ans.toString();
14    }
15}

JavaScript

1
2javascript
3class Solution {
4    removeDuplicates(S) {
5        let ans = [];
6        for(let c of S) {
7            if(ans.length != 0 && ans[ans.length - 1] == c)
8                ans.pop();  // remove the last character
9            else
10                ans.push(c);
11        }
12        return ans.join('');
13    }
14};

C++

1
2cpp
3class Solution {
4public:
5    string removeDuplicates(string S) {
6        string ans;
7        for (char c : S)
8            if (!ans.empty() && ans.back() == c)
9                ans.pop_back();  // remove the last character
10            else
11                ans.push_back(c);
12        return ans;
13    }
14};

C#

1
2csharp
3public class Solution {
4    public string RemoveDuplicates(string S) {
5        Stack<char> stack = new Stack<char>();
6        foreach (char c in S) {
7            if(stack.Count > 0 && stack.Peek() == c)
8                stack.Pop();  // remove the last character
9            else
10                stack.Push(c);
11        }
12        return new string(stack.ToArray().Reverse().ToArray());
13    }
14}

These snippets of code utilize a data structure called a Stack. A Stack works on the principle of 'Last in, First out'. Meaning, the most recent item added to the Stack is the first one to be removed. This is an efficient way to approach this problem as it allows us to keep track of our 'answer string' without needing to continually modify it. Instead, we can simply add each character of the input string to the Stack, and if we notice an 'adjacent duplicate' (by comparing the current character with the last one pushed to the Stack), we can pop the duplicate off the Stack. Finally, we convert the Stack back into a string, reversing the order of the characters as we go since Stacks are 'Last in, First out'.

By implementing it in this way, we can provide a solution that works consistently across multiple programming languages, including Python, JavaScript, Java, C++, and C#. This highlights both the flexibility and power of the Stack data structure for solving this type of problem and the versatility of these languages for supporting such data structures.

Note: C++ includes a string method back() which returns reference to the end character of the string. This helps us to get the last character of the string like using indexing in python/javaScript, It's the standard part of Library (STL).

In conclusion, understanding how to work with data structures like Stacks and their behaviors can enable us to solve a wide range of programming problems in multiple languages with elegant and efficient solutions.