← Grammarly Interview Insights

Grammarly·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Interviewed for a software engineering role at Grammarly and got a string manipulation problem that looked deceptively simple. The stack approach clicked for me eventually but I fumbled explaining the time complexity at first.

Questions Asked (1)

Q1

Given a string of lowercase letters, repeatedly remove adjacent duplicate characters until no more removals are possible. Return the resulting string. Walk through an O(n) stack-based solution.

Algorithms & Data Structures
Author's notes

My first instinct was to loop and splice, which is obviously not O(n).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose a stack-based solution that processes each character once. Explain how the stack naturally handles adjacent duplicates by comparing the current character with the top of the stack, and analyze the O(n) time and space complexity.

Pro tip: Mention that the stack approach is optimal because it processes each character exactly once and uses O(n) space, and note that the result is built in reverse order if using a stack, so you may need to reverse it or use a StringBuilder as a stack.

1. Clarify the problem

Restate the problem in your own words and ask clarifying questions about edge cases, such as empty string, all duplicates, or no duplicates. Confirm that removals are repeated until no adjacent duplicates remain.

2. Discuss brute force and its inefficiency

Briefly mention that a naive approach of repeatedly scanning and removing duplicates would be O(n^2) in the worst case, motivating the need for a more efficient solution.

3. Introduce the stack-based approach

Explain that you will use a stack (or a StringBuilder as a stack) to build the result. Iterate through each character: if the stack is not empty and the top equals the current character, pop; otherwise, push the current character.

4. Walk through an example

Choose a small example like 'abbaca' and step through the algorithm, showing how the stack evolves and the final result is obtained. This demonstrates understanding and catches off-by-one errors.

5. Analyze complexity and edge cases

State that the time complexity is O(n) because each character is pushed and popped at most once, and space complexity is O(n) for the stack. Mention edge cases like empty string, single character, and strings with no duplicates.

Key Points to Mention

  • Stack data structure for LIFO behavior to handle adjacent duplicates
  • Single pass through the string with O(n) time complexity
  • Space complexity O(n) due to stack storage
  • Using StringBuilder as a stack for efficiency in languages like Java
  • Handling edge cases: empty string, all same characters, no duplicates
  • The result may need to be reversed if using a stack, or use a StringBuilder to avoid reversal

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