Is Remove All Adjacent Duplicates in String II easy or hard?

The problem is rated Medium because the main challenge is recognizing the need to track consecutive runs efficiently. Once the stack pattern is identified, the implementation becomes straightforward and runs in linear time.

Remove All Adjacent Duplicates in String II Python/Java solution

Most implementations store (character, count) pairs in a stack. In Python, a list works well as the stack, while Java commonly uses an ArrayDeque or custom pair structure. Both implementations process the string in O(n) time.

How to solve Remove All Adjacent Duplicates in String II in O(n)?

Scan the string once while tracking consecutive character counts. Use a stack or an in-place array with a write pointer to store characters and their frequencies. When the count reaches k, remove that block immediately by popping from the stack or rewinding the write pointer.

What is the best approach for Remove All Adjacent Duplicates in String II?

The stack-based approach is the most reliable solution. While scanning the string, store pairs of (character, frequency) on a stack and remove entries when the count reaches k. Each character is processed once, giving O(n) time complexity and O(n) space.

Is Remove All Adjacent Duplicates in String II asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Amazon, Google, and Meta because it tests string processing, stack usage, and linear-time optimization. The problem also evaluates whether candidates can track frequency runs efficiently.

What data structure is used in Remove All Adjacent Duplicates in String II?

A stack is the primary data structure used to track characters and their consecutive counts. Some optimized implementations simulate the stack using arrays and two pointers, but the underlying concept is still stack-based run tracking.

What is the time complexity of Remove All Adjacent Duplicates in String II?

The optimal algorithms run in O(n) time where n is the length of the string. Each character is pushed to and possibly popped from a stack once, so the total number of operations remains linear. Space complexity is typically O(n) for storing intermediate characters.

Description Hints 2 Solution Video 13:05

1209. Remove All Adjacent Duplicates in String II

Medium61.7% acceptance18 companies

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

1 <= s.length <= 10⁵
2 <= k <= 10⁴
s only contains lowercase English letters.

Asked at 18 companies

Agoda Attentive FactSet Grammarly Disney Couchbase Bloomberg Oracle Salesforce Walmart Labs Tiktok Goldman Sachs

+6 more

PayPal Morgan Stanley Amazon Meta Microsoft

Google

Topics

Stack String

Hints open one at a time

Hint 1

Use a stack to store the characters, when there are k same characters, delete them.

Hint 2

To make it more efficient, use a pair to store the value and the count of each character.

13:05

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution