Remove adjacent duplicate groups repeatedly

Q: Remove adjacent duplicate groups repeatedly

This question evaluates string-manipulation skills, use of auxiliary data structures, and algorithmic complexity analysis when repeatedly removing contiguous identical groups.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a string s, repeatedly delete any maximal contiguous group of identical characters whose length is at least 2. After each deletion, the remaining parts concatenate and the process continues until no such group exists. Return the final string. Example: s = "abbba" → delete "bbb" → "aa" → delete "aa" → "". Design an O(n) time algorithm with O(n) extra space (e.g., using a stack-like technique), explain correctness, and analyze time/space complexity. Follow-up: generalize to delete groups of length ≥ k for a given k ≥ 2 while maintaining near-linear performance.

Remove adjacent duplicate groups repeatedly

Overview

Comments (0)