1047. Remove All Adjacent Duplicates In String

 

Remove All Adjacent Duplicates In String

Problem Description

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 <= 105
• s consists of lowercase English letters.

Approach (Using Stack)

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function(s) {
   const stack = [];
	for (let i = 0; i < s.length; i++) {
		const cv = s[i];
		const top = stack[stack.length - 1];

		// if last element is same as current pop off from stack
		if (cv === top) stack.pop();
		else stack.push(cv); // if not equal, add to stack
	}

	return stack.join('');
};

Complexity analysis.

Time Complexity

    We are traversing through the complete array which needs O(N).

Space Complexity

    We are using a stack as an extra space, hence space complexity is O(N).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1047. Remove All Adjacent Duplicates In String

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!