Remove All Adjacent Duplicates in String II

Let's analyze the problem. We are given a string s and an integer k. We need to remove k adjacent and equal characters from s repeatedly until no such removal is possible. The problem guarantees a unique answer. The constraints are that the length of s is up to 10^5 and k is up to 10^4.

Brute Force Approach

A brute-force approach would involve repeatedly scanning the string for sequences of k identical characters and removing them. This process continues until no more such sequences are found.

1. Scan the String: Iterate through the string to find consecutive characters that are the same.
2. Check for k Duplicates: If k adjacent characters are identical, remove them.
3. Repeat: Continue the process until no more removals can be made.

Code (Python):

def remove_duplicates_brute_force(s: str, k: int) -> str:
    while True:
        removed = False
        new_s = ""
        count = 1
        for i in range(len(s)):
            if i > 0 and s[i] == s[i - 1]:
                count += 1
            else:
                if i > 0 and count != k:
                    new_s += s[i - 1] * count
                elif count == k:
                    removed = True
                count = 1
        if count != k and len(s) > 0:
            new_s += s[-1] * count
        elif count == k:
            removed = True
        s = new_s

        if not removed:
            break
    return s

Time Complexity: O(N * (N / K)), where N is the length of the string. In the worst case, we might have to scan the entire string multiple times. Space Complexity: O(N), as we create new strings in each iteration.

This brute-force solution will be inefficient for large strings and values of k due to repeated string construction and scanning.

Optimal Approach: Using a Stack

An optimized solution uses a stack to keep track of characters and their counts. This approach allows us to process the string in a single pass.

1. Stack Element: Each element in the stack will be a pair (character, count).
2. Iterate Through String:
   • If the current character is the same as the top of the stack, increment the count.
   • If the count becomes equal to k, pop the element from the stack.
   • If the current character is different, push a new element (character, 1) onto the stack.
3. Construct Result: After processing the entire string, build the result string from the stack.

Code (Python):

def remove_duplicates_optimal(s: str, k: int) -> str:
    stack = []  # (char, count)

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

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

    return result

Time Complexity: O(N), where N is the length of the string. We iterate through the string once. Space Complexity: O(N), in the worst case, the stack might contain all characters of the string if no removals are possible.

Edge Cases

• Empty string: The code should handle empty strings correctly, returning an empty string.
• k = 1: If k is 1, all characters should be removed, resulting in an empty string.
• String with no duplicates: The code should return the original string.
• Large string with large k: The optimal solution is efficient and handles large strings and k values.

Summary

The optimal approach using a stack provides an efficient solution to the k-duplicate removal problem with O(N) time complexity and O(N) space complexity. It avoids the repeated string construction of the brute-force approach, making it suitable for large input strings.