Feature Rollout Rollback
A feature-flag service records every rollout action as a single line: ENABLE name, DISABLE name, or ROLLBACK. ROLLBACK undoes the most recent action that has not already been rolled back. After processing the log, you must report the final set of enabled features.
Problem
You are given a sequence of operations. Each operation is one of: ENABLE x, DISABLE x, or ROLLBACK. ENABLE x marks feature x as enabled. DISABLE x marks feature x as disabled. ROLLBACK reverts the most recent non-rollback action (an ENABLE becomes a no-op, a DISABLE becomes a no-op). After all operations, return the sorted list of feature names that are currently enabled.
Input
An integer n (1 ≤ n ≤ 10^5) followed by n operations. Feature names are lowercase ASCII up to 32 chars.
Output
The sorted list of enabled feature names after processing all operations.
Constraints
- 1 ≤ n ≤ 100,000
- ROLLBACK with nothing to undo is a no-op
- Toggling the same feature multiple times is allowed
- Two consecutive ROLLBACKs undo the two most recent non-rollback actions, in reverse order
Examples
Example 1
Input
6 ENABLE search ENABLE checkout DISABLE checkout ROLLBACK ROLLBACK ENABLE profile
Output
profile search
After ENABLE search → {search}. ENABLE checkout → {search, checkout}. DISABLE checkout → {search}. ROLLBACK undoes DISABLE → {search, checkout}. ROLLBACK undoes ENABLE checkout → {search}. ENABLE profile → {search, profile}.