The challenge
Repeatedly remove pairs of equal adjacent characters until none remain.
ASCII letters; an empty result is the empty string.
Example
abbaca → ca.
Use the walkthrough below to inspect the input and each state change.
See Remove Adjacent Duplicates, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 8
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: ["a","b","b","a","c","a"]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
The stack holds the already-reduced prefix.
Indices are zero-based. C++ uses C++17 or later.
def solve(values):
stack = []
for c in values:
if stack and stack[-1] == c: stack.pop()
else: stack.append(c)
return ''.join(stack)
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
string solve(const vector<string>& values) {
string stack;
for (const auto& c : values) {
if (!stack.empty() && stack.back() == c[0]) stack.pop_back();
else stack += c;
}
return stack;
}