Break Adjacent Duplicate Characters

Question

The question asks the candidate to write a function that removes adjacent duplicate characters from a given string, returning the modified string.

Codemia · Accepted Answer

To solve the problem of removing adjacent duplicate characters, we can use a stack data structure. The idea is to iterate through each character in the string and use the stack to keep track of the characters that are not duplicates. If the current character is the same as the top character of the stack, we skip adding it to the stack; otherwise, we push it onto the stack.

Here is a step-by-step breakdown of the algorithm:
1. Initialize an empty stack.
2. Loop through each character in the input string.
3. For each character, check if the stack is not empty and if the top of the stack is the same as the current character.
4. If they are the same, skip adding the current character. If they are different, push the current character onto the stack.
5. Finally, join the characters in the stack to form the resulting string without adjacent duplicates.

The time complexity of this algorithm is O(n), where n is the length of the input string, as we are iterating through the string once. The space complexity is O(n) in the worst case, where all characters are unique and stored in the stack.

Here is the Python code implementing the above algorithm:
```python
def remove_adjacent_duplicates(s):
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            continue
        stack.append(char)
    return ''.join(stack)
```
This function takes a string `s` as input and returns a new string with adjacent duplicates removed.

When implementing this solution, it is important to consider edge cases. For example:
- An empty string should return an empty string.
- A string with no adjacent duplicates should return the original string unchanged.
- Strings with all identical characters should return a single character.

Break Adjacent Duplicate Characters

IBM

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

IBM Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string