Remove All Adjacent Duplicates In String

Easy

Google

1 view

Topics:

StringsStacks

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^5
s consists of lowercase English letters.

Remove All Adjacent Duplicates In String

Easy

Google

1 view

Topics:

StringsStacks

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^5
s consists of lowercase English letters.

Solution

Naive Solution

A brute-force approach would involve iterating through the string and, for each pair of adjacent characters, checking if they are equal. If they are, remove them and repeat the process until no more duplicate removals can be made. This involves potentially recreating the string multiple times.

def remove_duplicates_naive(s):
    while True:
        original_length = len(s)
        new_s = ""
        i = 0
        while i < len(s):
            if i + 1 < len(s) and s[i] == s[i+1]:
                i += 2
            else:
                new_s += s[i]
                i += 1
        s = new_s
        if len(s) == original_length:
            break
    return s

Big O Analysis:

Time Complexity: O(N^2) in the worst case. In each iteration, we scan the string (O(N)), and in the worst-case scenario (e.g., 'aaaaaa'), we might need to iterate multiple times. This results in O(N * N) = O(N^2)
Space Complexity: O(N), since a new string is created in each iteration.

Optimal Solution: Using a Stack

A more efficient solution utilizes a stack data structure. Iterate through the string; if the current character is the same as the top of the stack, pop the stack (effectively removing the duplicate). Otherwise, push the character onto the stack. The final result is the string formed by the characters remaining in the stack.

def remove_duplicates_stack(s):
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return "".join(stack)

Big O Analysis:

Time Complexity: O(N), where N is the length of the string. Each character is visited once.
Space Complexity: O(N), where N is the length of the string. In the worst case (no duplicates), the stack can grow to the same size as the input string.

Edge Cases

Empty String: An empty input string should return an empty string.
String with no duplicates: Input such as "abc" should return "abc".
String with all duplicates: Input such as "aaaa" should return "".
String with mixed duplicates: Input such as "abbaca" should return "ca".

Solution

Naive Solution

def remove_duplicates_naive(s):
    while True:
        original_length = len(s)
        new_s = ""
        i = 0
        while i < len(s):
            if i + 1 < len(s) and s[i] == s[i+1]:
                i += 2
            else:
                new_s += s[i]
                i += 1
        s = new_s
        if len(s) == original_length:
            break
    return s

Big O Analysis:

Time Complexity: O(N^2) in the worst case. In each iteration, we scan the string (O(N)), and in the worst-case scenario (e.g., 'aaaaaa'), we might need to iterate multiple times. This results in O(N * N) = O(N^2)
Space Complexity: O(N), since a new string is created in each iteration.

Optimal Solution: Using a Stack

def remove_duplicates_stack(s):
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return "".join(stack)

Big O Analysis:

Time Complexity: O(N), where N is the length of the string. Each character is visited once.
Space Complexity: O(N), where N is the length of the string. In the worst case (no duplicates), the stack can grow to the same size as the input string.

Edge Cases

Empty String: An empty input string should return an empty string.
String with no duplicates: Input such as "abc" should return "abc".
String with all duplicates: Input such as "aaaa" should return "".
String with mixed duplicates: Input such as "abbaca" should return "ca".