Remove All Adjacent Duplicates In String II Leetcode 1209 [Python]

In this blog post, we’re going to tackle the Remove All Adjacent Duplicates In String II problem from LeetCode.

In simple terms, if you encounter k consecutive characters in s, remove them!

This is a medium difficulty problem in the category of Stack, and it’s one of those problems that require an efficient approach.

We’ll provide a Python solution that optimally handles this problem, not that any one doesn’t.

Problem Overview

The problem statement is as follows:

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 right sides of the deleted substring to concatenate together.

You repeatedly make k duplicate removals on s until you no longer can.

The goal is to 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”, getting “ddbbbdaa”.
– Then delete “bbb”, getting “dddaa”.
– Finally, delete “ddd”, getting “aa”.

Example 3:

Input:
s = "pbbcggttciiippooaais", k = 2

Output:
"ps"

Understanding the Constraints

Before we dive into the solution, it’s essential to understand the constraints given in the problem:

1 <= s.length <= 105: The input string s can have a maximum length of 105 characters.
2 <= k <= 104: The integer k is between 2 and 104.
s only contains lowercase English letters: The input string consists of lowercase English letters, so we don’t need to consider other characters.

Remove All Adjacent Duplicates In String II LeetCode Problem Solution

Let’s start by providing a Python solution for this problem.

We’ll break it down into different sections, including the bruteforce approach and an efficient approach using a stack.

1. Bruteforce Approach

The bruteforce approach involves repeatedly scanning the string to find and remove adjacent duplicate substrings of length k.

This process continues until no more duplicates can be removed.

It is less efficient, with a time complexity of O(n^2) in the worst case, where ‘n’ is the length of the string.

def removeDuplicatesBruteforce(s: str, k: int) -> str:
    while True:
        # Initialize variables to keep track of changes.

        changed = False
        i = 0
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            if j - i >= k:
                s = s[:i] + s[j:]
                changed = True
            i = j
        if not changed:
            break
    return s

In this approach, we keep scanning the string and removing duplicates until no more changes can be made.

It works, but it’s not the most efficient solution for large strings.

2. Efficient Approach with a Stack

The more efficient approach involves using a stack to keep track of characters and their counts.

We’ll iteratively process the string, and when we encounter ‘k’ consecutive characters, we’ll remove them.

This approach has a time complexity of O(n) and is significantly more efficient.

def removeDuplicates(s: str, k: int) -> str:
    stack = []  # We'll use a stack to keep track of characters and their counts.

for c in s:
        if stack and stack[-1][0] == c:
            stack[-1][1] += 1
        else:
            stack.append([c, 1])
        
        if stack[-1][1] == k:
            stack.pop()
    
    res = ""
    for char, count in stack:
        res += char * count
    
    return res

This approach allows us to process the string efficiently and remove adjacent duplicates as soon as they are encountered.

The use of a stack simplifies the process, and we only need to iterate through the string once.

Python Code Solution

Now, this is the efficient approach on Leetcode:

View on GitHub ➹

def removeDuplicates(s: str, k: int) -> str:
    stack = []  # We'll use a stack to keep track of characters and their counts.

for c in s:
        if stack and stack[-1][0] == c:
            stack[-1][1] += 1
        else:
            stack.append([c, 1])

        if stack[-1][1] == k:
            stack.pop()

    res = ""
    for char, count in stack:
        res += char * count

    return res

Time and Space Complexity

Now, let’s analyze the time and space complexity of our efficient approach:

Time Complexity: O(n) – We iterate through the string ‘s’ once, where ‘n’ is the length of the string.
Space Complexity: O(n) – We use a stack to store characters and their counts, which can have a maximum of ‘n’ elements.

Reasoning Behind Our Approach

The reasoning behind our efficient approach is based on using a stack data structure to keep track of characters and their counts as we process the input string.

By doing this, we can identify and remove adjacent duplicates as soon as they are encountered.

The key insights are as follows:

We don’t need to scan the entire string repeatedly.

Instead, we process it linearly.
– When we encounter ‘k’ consecutive characters, we remove them efficiently from the stack.
– Using a stack allows us to handle characters and counts effectively.

Conclusion

In this blog post, we’ve discussed the Remove All Adjacent Duplicates In String II problem on LeetCode.

We provided a Python solution that efficiently removes adjacent duplicates using a stack data structure.

This approach ensures a time complexity of O(n), making it a practical solution for large strings.

If you found this post helpful, please like and engage to support the our platform.

Additionally, if you’re preparing for coding interviews, consider checking out Auditorical, a free resource created to help you in your interview preparations.

Feel free to comment, ask questions, make suggestions, and share this content with others who might find it useful.

For more details, you can refer to the problem on LeetCode.

Happy coding!