What is the time complexity of Remove All Adjacent Duplicates In String?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Remove All Adjacent Duplicates In String?

This problem uses String, Stack. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Remove All Adjacent Duplicates In String?

**Leveraging the stack's LIFO for 'effective adjacency':** A stack's Last-In, First-Out (LIFO) property is perfectly suited here. The `stack[-1]` (or `peek()` operation) always provides the most recently added character that *has not yet been removed*. This character is precisely the one that is 'effectively adjacent' to the current character being processed from the input string, allowing for immediate duplicate detection and removal. **Greedy, sequential processing handles cascading removals:** The solution processes the input string strictly from left to right. When a duplicate is found (current character matches `stack[-1]`), both are effectively discarded by popping from the stack and not pushing the current character. This 'backs up' our effective string, automatically allowing previously non-adjacent characters to become new neighbors, thus correctly handling the cascading nature of duplicate removals (e.g., 'abccba' -> 'abba' -> 'aa' -> '').

Which companies ask LeetCode 1047. Remove All Adjacent Duplicates In String in interviews?

This problem is frequently asked at Geico, Grammarly, Paytm, Whatnot, Zoho.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Remove All Adjacent Duplicates In String - LeetCode 1047 Solution

Remove All Adjacent Duplicates In String - Complete Solution Guide

Remove All Adjacent Duplicates In String is LeetCode problem 1047, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 . 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

Detailed Explanation

This problem asks us to systematically reduce a given string by repeatedly identifying and removing any pair of adjacent, identical lowercase English letters. The process is not a one-shot pass; removing one duplicate pair might cause two previously separated characters to become adjacent, potentially forming a new duplicate pair that then also needs to be removed. For example, given "abbaca", the first step would likely remove "bb" to yield "aaca". Following this, the now adjacent "aa" would be removed, resulting in the final string "ca".

Solution Approach

The provided solution elegantly tackles this problem using a stack. The core idea is to process the input string characters one by one, building up a new string (conceptually represented by the stack) where all adjacent duplicates have been eliminated. When we encounter a character from the input string, we compare it against the character currently at the 'end' of our partially built result string. The stack's top element conveniently represents this 'end' character.

Step-by-Step Algorithm

Step 1: Initialize an empty stack (or string builder).
Step 2: Iterate through the input string character by character.
Step 3: If the stack is not empty and the current character is equal to the top of the stack (or last character in the string builder), pop the top element from the stack (or remove the last character from the string builder).
Step 4: Otherwise, push the current character onto the stack (or append it to the string builder).
Step 5: After iterating through all characters, convert the stack contents (or string builder content) back into a string and return it.

Key Insights

**Leveraging the stack's LIFO for 'effective adjacency':** A stack's Last-In, First-Out (LIFO) property is perfectly suited here. The `stack[-1]` (or `peek()` operation) always provides the most recently added character that *has not yet been removed*. This character is precisely the one that is 'effectively adjacent' to the current character being processed from the input string, allowing for immediate duplicate detection and removal.
**Greedy, sequential processing handles cascading removals:** The solution processes the input string strictly from left to right. When a duplicate is found (current character matches `stack[-1]`), both are effectively discarded by popping from the stack and not pushing the current character. This 'backs up' our effective string, automatically allowing previously non-adjacent characters to become new neighbors, thus correctly handling the cascading nature of duplicate removals (e.g., 'abccba' -> 'abba' -> 'aa' -> '').
**Efficient result construction without intermediate string overhead:** Instead of repeatedly building new substrings or concatenating strings (which can be computationally expensive, potentially leading to `O(N^2)` complexity if not careful), the stack merely performs `append` and `pop` operations on individual characters. The final, de-duplicated string is only constructed once at the very end by joining the characters left in the stack, making the overall process efficient.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: String, Stack.

Companies

Asked at: Geico, Grammarly, Paytm, Whatnot, Zoho.

Remove All Adjacent Duplicates In String | LeetCode 1047

Easy

String Stack

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) {
                sb.deleteCharAt(sb.length() - 1);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1047: Remove All Adjacent Duplicates In String - Detailed explanation and solution approaches.

Topics

String Stack

Companies

GeicoGrammarlyPaytmWhatnotZoho

Stats

Difficulty:Easy

Languages:4

Companies:5

Problem #:1047

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize an empty stack (or string builder).
2
Step 2: Iterate through the input string character by character.
3
Step 3: If the stack is not empty and the current character is equal to the top of the stack (or last character in the string builder), pop the top element from the stack (or remove the last character from the string builder).
4
Step 4: Otherwise, push the current character onto the stack (or append it to the string builder).
5
Step 5: After iterating through all characters, convert the stack contents (or string builder content) back into a string and return it.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The algorithm iterates through each character of the string exactly once. The space used is proportional to the maximum number of characters that can be stored in the stack, which in the worst case (no duplicates) is equal to the length of the input string.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach

Recursively remove adjacent duplicates. This would involve repeatedly calling a function that checks for and removes adjacent duplicates until no more removals are possible.

Time: O(n^2) in the worst caseSpace: O(n) due to the recursive call stack.

Trade-offs: Less efficient than the iterative stack-based approach. The iterative approach is preferred for its better time complexity.

✨

Key Insights

1**Leveraging the stack's LIFO for 'effective adjacency':** A stack's Last-In, First-Out (LIFO) property is perfectly suited here. The `stack[-1]` (or `peek()` operation) always provides the most recently added character that *has not yet been removed*. This character is precisely the one that is 'effectively adjacent' to the current character being processed from the input string, allowing for immediate duplicate detection and removal.
2**Greedy, sequential processing handles cascading removals:** The solution processes the input string strictly from left to right. When a duplicate is found (current character matches `stack[-1]`), both are effectively discarded by popping from the stack and not pushing the current character. This 'backs up' our effective string, automatically allowing previously non-adjacent characters to become new neighbors, thus correctly handling the cascading nature of duplicate removals (e.g., 'abccba' -> 'abba' -> 'aa' -> '').
3**Efficient result construction without intermediate string overhead:** Instead of repeatedly building new substrings or concatenating strings (which can be computationally expensive, potentially leading to `O(N^2)` complexity if not careful), the stack merely performs `append` and `pop` operations on individual characters. The final, de-duplicated string is only constructed once at the very end by joining the characters left in the stack, making the overall process efficient.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty input string (""). The solution handles this gracefully; the stack remains empty, and an empty string is returned.
Edge case 2: String with no adjacent duplicates. In this scenario, all characters are pushed onto the stack, and the final string will be identical to the input string.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the empty string case. The code should gracefully handle an empty input string.

✗Common mistake 2: Incorrectly implementing the stack operations (push and pop) or misusing a string builder as a stack. Beginners might struggle with the stack's LIFO nature.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data compression. Removing adjacent duplicates is a simple form of run-length encoding, used to reduce data size.

🏦Real-world scenario 2: Text processing and cleaning. This algorithm could be used to pre-process text data by removing redundant characters before further analysis.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 26, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 30

❓

Frequently Asked Questions

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

What is a monotonic stack and when should I use it?

A monotonic stack maintains elements in sorted order (increasing or decreasing). Use it for "next greater element," "largest rectangle," or "stock span" problems. It achieves O(n) time by avoiding redundant comparisons through maintaining order invariants.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Remove All Adjacent Duplicates In String"?

For this easy-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?