Remove All Adjacent Duplicates In String

Data Structures and Algorithms

Statement

Given a string consisting of lowercase English characters, repeatedly remove adjacent duplicate characters, one pair at a time. Both members of a pair need to be removed.

Constraints

• 1 ≤ string.length() ≤ 10³
• string consists of lowercase English characters

Solution

"""
production algorithm
"""


class Solution:
    def remove_duplicates(self, string):
        """
        time complexity O(n)
        space complexity O(1)
        """
        stack = list()

        for character in string:
            if stack and stack[-1] == character:
                stack.pop()
            else:
                stack.append(character)

        return str().join(stack)

"""
unit tests
"""

from unittest import TestCase
from algorithms.stacks.remove_all_adjacent_duplicates_in_string.solution import Solution


class SolutionTestCase(TestCase):
    def test_duplicates_removed(self):
        # Given
        string = "wxxyyz"
        solution = Solution()

        # When
        actual = solution.remove_duplicates(string)

        # Then
        expected = "wz"
        self.assertEqual(actual, expected)

    def test_duplicates_separated_by_duplicates_removed(self):
        # Given
        string = "uvwwvxyyxz"
        solution = Solution()

        # When
        actual = solution.remove_duplicates(string)

        # Then
        expected = "uz"
        self.assertEqual(actual, expected)

Strategy

Stacks.

Explanation

A stack is created to be used to hold characters that will be matched for duplicates. Then, the characters of the string are iterated. If the stack is empty, then push the current character to the top of the stack; after all it can’t be a duplicate (yet) because the stack is empty. Otherwise the stack isn’t empty, so compare the current character to the top of the stack. If the current character and the top of the stack match, then the characters are duplicates, and so pop the top of the stack to remove the duplicates from the input string.

After iteration of all characters completes, there will be no consecutive duplicates in the characters. Stringify the stack and return the result.

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of characters in the string.

Space Complexity

At worst, the stack holds every character of the string, which is a size proportional to n. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/stacks/remove_all_adjacent_duplicates_in_string at main ·…