Cancel out the doubled keystrokes
A faulty keyboard doubles a letter now and then. The cleaner removes any two identical letters sitting next to each other, and keeps going while that leaves a new pair behind.
- Two identical characters next to each other both disappear.
- Removing a pair can bring two more together, and those go too.
- Keep going until no adjacent pair is left.
- Text with nothing to remove comes back unchanged.
collapseDoubles(typed: string) → string
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
std::string collapseDoubles(std::string typed) {
}Worked examples
| Call | Result |
|---|---|
collapseDoubles(std::string("abbaca")) | std::string("ca") |
collapseDoubles(std::string("azxxzy")) | std::string("ay") |
collapseDoubles(std::string("abc")) | std::string("abc") |
collapseDoubles(std::string("aa")) | std::string("") |
Hint
Build the result on a stack. For each character, either it cancels the one on top or it goes on top — no rescanning needed.
Reference solution in C++
std::string collapseDoubles(std::string typed) {
std::string kept;
for (char ch : typed) {
if (!kept.empty() && kept.back() == ch) kept.pop_back();
else kept.push_back(ch);
}
return kept;
}