Meta·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Meta SWE coding round, one problem the whole session. The question looked like a simple string cleanup at first glance but the O(n) constraint with cascading collapses is where things got real.

Questions Asked (1)

Given a string and an integer k (k >= 2), repeatedly remove every maximal contiguous group of identical characters whose length is at least k. After each removal, the string collapses and the process repeats until no more removals are possible. Return the final string. Design an O(n) time and O(n) space solution using a stack.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I got the brute force out fast, simulate each pass until stable, but then they asked for O(n) and I kind of stared at the screen for a moment.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack where each element stores a character and its current run length. Iterate through the string, pushing or updating the top element; when the run length reaches k, pop it. At the end, reconstruct the string from the stack.

Pro tip: Emphasize that the stack approach naturally handles cascading removals because after popping, the new top may have the same character as the next incoming character, and the run length will be correctly updated. Also, mention that storing run lengths avoids storing every character, keeping space O(n) in the worst case but often much less.

1. Clarify the problem and constraints

Restate the problem to ensure understanding: repeatedly remove maximal contiguous groups of length >= k, with collapsing after each removal. Confirm that k >= 2 and that the solution must be O(n) time and O(n) space.

2. Design the stack-based approach

Propose using a stack where each element is a pair (character, count). Iterate through the string, and for each character, compare with the top of the stack. If same, increment count; if different, push new pair with count 1. If count reaches k, pop the element.

3. Walk through an example

Trace the algorithm on a small example (e.g., s = "deeedbbcccbdaa", k = 3) to demonstrate how removals cascade and how the stack correctly handles them.

4. Analyze time and space complexity

Explain that each character is processed once, and each stack operation is O(1), so total time is O(n). Space is O(n) in the worst case (e.g., no removals), but often less.

5. Discuss edge cases and trade-offs

Mention edge cases: empty string, k larger than string length, all characters same, and alternating characters. Compare with a naive repeated-pass approach (O(n^2)) to highlight the efficiency of the stack solution.

Key Points to Mention

Stack elements store character and run length to avoid storing every character individually.
When a run reaches length k, pop it, which may cause the new top to merge with the next character, handling cascading removals.
Time complexity is O(n) because each character is pushed and popped at most once.
Space complexity is O(n) in the worst case, but can be less if many removals occur.
The algorithm naturally handles overlapping removals and collapsing without multiple passes.
Edge cases: empty string, k > n, and strings with no removable groups.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.