Remove All Adjacent Duplicates
Easy About 10 min Free, no account needed
Keep deleting adjacent equal pairs until none remain.
The brief
Given a lowercase string s, repeatedly delete two adjacent equal letters
until no such pair remains, and return the result (it is unique regardless of
deletion order).
The obvious approach rescans and rebuilds the string after every deletion pass, O(n2) on inputs that collapse layer by layer, like the hidden 40,000-character "onion" that annihilates completely, so the repeated passes are too slow. You will need a single-pass approach, O(n).
Starter code
using System;
public class Solution
{
// TODO: return the string after all adjacent equal pairs are (repeatedly) removed.
public string RemoveDuplicates(string s)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Stacks
- Use last-in, first-out state for nesting, matching and expression evaluation.
Related katas
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.
- Roll Back the Payload Ledger Easy Free Track staged payload totals while nested checkpoints are opened and rolled back.
- Valid Parentheses Easy Free Are the brackets balanced and properly nested?
- Decode String Medium Free Expand k[encoded] patterns, nesting included.