Jobs

Interviews

Discussions

Remove All Adjacent Duplicates In String

Easy

Grammarly

3 views

Topics:

StringsStacksTwo Pointers

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

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

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

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy"
Output: "ay"

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Remove All Adjacent Duplicates In String

Easy

Grammarly

3 views

Topics:

StringsStacksTwo Pointers

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

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

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

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy"
Output: "ay"

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input string s?
Is the input string guaranteed to contain only lowercase English letters, or could there be other characters?
If after removing all adjacent duplicates, the resulting string is empty, should I return an empty string or null?
Are there any specific performance considerations or time complexity constraints that I should be aware of beyond aiming for the most optimal solution?
If multiple removal sequences lead to the same final string, is any such valid final string acceptable?

Brute Force Solution

Approach

The brute force approach tackles this problem by repeatedly scanning the string to find and remove adjacent duplicate characters. It keeps going until no more duplicates can be found. This method checks every possible pair of adjacent characters in each pass.

Here's how the algorithm would work step-by-step:

Begin by looking at the very first character in the string and the one right next to it.
If these two characters are the same, remove both of them from the string.
If they are not the same, move on to the next pair of adjacent characters.
Continue checking each pair of adjacent characters throughout the entire string, removing duplicates as you find them.
After checking all pairs in the string once, start over from the beginning of the (potentially modified) string.
Repeat this process of checking and removing adjacent duplicates until you can go through the entire string without finding any more duplicate pairs to remove.
The string you are left with at the end is the result.

Code Implementation

def remove_duplicates_brute_force(input_string):
    string_changed = True

    while string_changed:
        string_changed = False
        index = 0

        while index < len(input_string) - 1:
            # Check for adjacent duplicates

            if input_string[index] == input_string[index + 1]:
                # Remove the duplicate characters

                input_string = input_string[:index] + input_string[index + 2:]

                string_changed = True

                # Reset index to start from the beginning

                index = 0

            else:
                # Move to the next character

                index += 1

    return input_string

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach repeatedly iterates through the string, which has a length of n, to identify and remove adjacent duplicate characters. In the worst case, each iteration may remove only a few characters, requiring multiple passes through the string. Because the algorithm might need to iterate n times, and each iteration examines n adjacent pairs, the time complexity is approximately n * n operations, resulting in O(n²).

Space Complexity

O(1) – The brute force approach, as described, operates primarily by modifying the input string in-place. It doesn't explicitly create any auxiliary data structures like lists, stacks, or hash maps to store intermediate results or track visited characters. Although string manipulation might implicitly create copies depending on the language implementation, the algorithm's logic does not inherently require auxiliary space proportional to the input string length N. Therefore, the space complexity remains constant, independent of the input size N.

Optimal Solution

Approach

The best way to remove adjacent duplicate characters from a string is to use a temporary storage to remember the last seen character. This method efficiently removes duplicates by keeping track of characters.

Here's how the algorithm would work step-by-step:

Start by looking at the first character in the string.
If the character is the same as the last one you saw, remove the last character from your temporary storage.
If the character is different from the last one, add the current character to your temporary storage.
Move to the next character and repeat steps 2 and 3 until you have processed every character in the string.
The final result is the characters left in your temporary storage.

Code Implementation

def remove_adjacent_duplicates(input_string):
    temporary_storage = []

    for character in input_string:
        # Compare current char to the last in temporary_storage.
        if temporary_storage and character == temporary_storage[-1]:

            temporary_storage.pop()

        # Append when temporary_storage is empty or chars differ.
        else:

            temporary_storage.append(character)

    # Construct final string from the storage.
    return ''.join(temporary_storage)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input string of size n exactly once. In each iteration, we perform a constant-time operation: either appending to or removing from the temporary storage (stack). Since the number of operations is directly proportional to the input size n, the time complexity is O(n).

Space Complexity

O(N) – The provided solution uses a temporary storage (implicitly a stack or string builder) to store the processed characters. In the worst-case scenario, where there are no adjacent duplicates, each character from the input string will be added to the temporary storage. Therefore, the auxiliary space used grows linearly with the input size N, where N is the length of the input string. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately or throw an IllegalArgumentException based on the requirements.
String with a single character	Return the string as is, since no adjacent duplicates can exist.
String with only two characters that are duplicates	The algorithm should remove both characters, resulting in an empty string.
String with many repeating adjacent duplicates, such as 'aaaaaaa'	The algorithm must efficiently remove all adjacent duplicates until none remain.
String with interleaved duplicates, such as 'abccba'	The algorithm should correctly remove the 'cc' and result in 'abba', followed by removing 'bb' resulting in 'aa', and then removing 'aa' resulting in ''.
Very long string to test performance	The stack-based approach or iterative approach should provide efficient performance within the allowed time limit.
String with no duplicates at all	The algorithm should return the string unchanged.
String with characters other than lowercase English letters	Either return an error, throw an exception, or filter non-lowercase English characters before processing, based on problem constraints.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input string s?
Is the input string guaranteed to contain only lowercase English letters, or could there be other characters?
If after removing all adjacent duplicates, the resulting string is empty, should I return an empty string or null?
Are there any specific performance considerations or time complexity constraints that I should be aware of beyond aiming for the most optimal solution?
If multiple removal sequences lead to the same final string, is any such valid final string acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin by looking at the very first character in the string and the one right next to it.
If these two characters are the same, remove both of them from the string.
If they are not the same, move on to the next pair of adjacent characters.
Continue checking each pair of adjacent characters throughout the entire string, removing duplicates as you find them.
After checking all pairs in the string once, start over from the beginning of the (potentially modified) string.
Repeat this process of checking and removing adjacent duplicates until you can go through the entire string without finding any more duplicate pairs to remove.
The string you are left with at the end is the result.

Code Implementation

def remove_duplicates_brute_force(input_string):
    string_changed = True

    while string_changed:
        string_changed = False
        index = 0

        while index < len(input_string) - 1:
            # Check for adjacent duplicates

            if input_string[index] == input_string[index + 1]:
                # Remove the duplicate characters

                input_string = input_string[:index] + input_string[index + 2:]

                string_changed = True

                # Reset index to start from the beginning

                index = 0

            else:
                # Move to the next character

                index += 1

    return input_string

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first character in the string.
If the character is the same as the last one you saw, remove the last character from your temporary storage.
If the character is different from the last one, add the current character to your temporary storage.
Move to the next character and repeat steps 2 and 3 until you have processed every character in the string.
The final result is the characters left in your temporary storage.

Code Implementation

def remove_adjacent_duplicates(input_string):
    temporary_storage = []

    for character in input_string:
        # Compare current char to the last in temporary_storage.
        if temporary_storage and character == temporary_storage[-1]:

            temporary_storage.pop()

        # Append when temporary_storage is empty or chars differ.
        else:

            temporary_storage.append(character)

    # Construct final string from the storage.
    return ''.join(temporary_storage)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately or throw an IllegalArgumentException based on the requirements.
String with a single character	Return the string as is, since no adjacent duplicates can exist.
String with only two characters that are duplicates	The algorithm should remove both characters, resulting in an empty string.
String with many repeating adjacent duplicates, such as 'aaaaaaa'	The algorithm must efficiently remove all adjacent duplicates until none remain.
String with interleaved duplicates, such as 'abccba'	The algorithm should correctly remove the 'cc' and result in 'abba', followed by removing 'bb' resulting in 'aa', and then removing 'aa' resulting in ''.
Very long string to test performance	The stack-based approach or iterative approach should provide efficient performance within the allowed time limit.
String with no duplicates at all	The algorithm should return the string unchanged.
String with characters other than lowercase English letters	Either return an error, throw an exception, or filter non-lowercase English characters before processing, based on problem constraints.