Total Appeal Of A String - Leetcode Solution

Problem Statement:

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.

Solution:

The given problem can be solved using a stack data structure.

Initially, we can push the first character of the string into the stack. Then, for each subsequent character s[i] in the string, we can check if there is a duplicate of s[i] at the top of the stack. If there is a duplicate, we can pop it from the stack. Otherwise, we can push s[i] onto the stack.

After iterating through the entire string, the remaining characters in the stack can be combined to form the final string.

The time complexity of this solution is O(n), where n is the length of the string.

Code:

Here is the Python code implementing the above solution:

def removeDuplicates(s: str) -> str: stack = [] for ch in s: if stack and stack[-1] == ch: stack.pop() else: stack.append(ch) return ''.join(stack)

Explanation:

In the above code, we create an empty stack and iterate through the characters in the string s. If the stack is not empty and the top of the stack is equal to the current character, we pop the top element from the stack. Otherwise, we push the current character onto the stack.

Finally, we join the characters in the stack to form the final string and return it.

Example:

Input: "abbaca" Output: "ca"

Explanation:

We start with "a" in the stack.

Then, we encounter "b" which is not equal to "a", so we push it onto the stack. Stack is now ["a", "b"].

Next, we encounter another "b" which is equal to the top of the stack "b", so we pop it. Stack is now ["a"].

Then, we encounter "a" which is equal to the top of the stack, so we pop it. Stack is now empty.

We push "c" onto the stack. Stack is now ["c"].

Finally, we encounter "a" which is not equal to the top of the stack "c", so we push it onto the stack. Stack is now ["c", "a"].

The remaining characters in the stack "ca" are combined to form the final string "ca".

1