Remove All Adjacent Duplicates In String solution and explanation
Deloitte
Cisco
Google
9 more videos on this problem
LeetCode Remove All Adjacent Duplicates In String Solution Explained - JavaNick White · 8:10 · 30K views
REMOVE ADJACENT DUPLICATE IN STRING | PYTHON | LEETCODE # 1047Cracking FAANG · 7:18 · 4K views
LeetCode 1047: Remove All Adjacent Duplicates In StringEngineering Digest · 4:31 · 3K views
Leetcode | 1047. Remove All Adjacent Duplicates In String | Easy | Java SolutionDeveloper Docs · 4:25 · 2K views
Remove All Adjacent Duplicates In String - LeetCode 1047 - JavaScriptAlgoJS · 4:07 · 1K views
Remove All Adjacent Duplicates In String | Leetcode 1047 | Live coding sessionCoding Decoded · 7:27 · 748 views
LeetCode 1047 : Remove All Adjacent Duplicates In String || EASY || JAVA || Detailed SolutionCodeGPT · 8:24 · 579 views
Remove All Adjacent Duplicates In String - LeetCode #1047 with python programmingCodingNinja · 8:07 · 527 views
Leetcode 1047. Remove All Adjacent Duplicates In String PythonTechZoo · 4:00 · 504 views
Leetcode # 1047. Remove All Adjacent Duplicates In StringSumanshu Nankana · 7:04 · 398 views
The problem
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 <= 105sconsists of lowercase English letters.
Approach overview
Problem Overview: Given a string s, repeatedly remove pairs of adjacent duplicate characters until no such pairs remain. The final string must contain no two neighboring characters that are equal. The challenge is handling cascading removals where deleting one pair exposes another.
Approach 1: Stack-Based Approach (O(n) time, O(n) space)
This problem maps naturally to a stack. Iterate through the string character by character. For each character, compare it with the top of the stack. If they match, pop the stack because the pair cancels out. If they differ, push the current character onto the stack. This simulates the repeated removal process without actually modifying the string multiple times.
The key insight: the stack always stores the current valid result with no adjacent duplicates. When a duplicate appears, the top element represents the previous character, so you can remove the pair instantly. Each character is pushed and popped at most once, giving O(n) time complexity and O(n) space for the stack. This approach is straightforward and widely used in interview solutions involving adjacent cancellation problems.
Approach 2: Two-Pointer Approach (O(n) time, O(1) extra space)
You can simulate the stack using two pointers on a character array. Convert the string into an array and maintain a write pointer that represents the end of the current valid result. Iterate through the array with a read pointer. For each character, write it to the position indicated by the write pointer.
After writing, check whether the last two characters in the result are equal. If they match, move the write pointer back by two positions, effectively removing the pair. Otherwise, advance the pointer normally. This technique uses the input array itself as the stack buffer.
This method still processes each character once, so the time complexity remains O(n). Since it modifies the array in place, the extra memory overhead is O(1). It's a great example of using pointer manipulation in string processing and often preferred when minimizing memory allocations.
Recommended for interviews: The stack-based solution is the most commonly expected answer because it directly models the removal behavior and clearly demonstrates understanding of stack operations like push and pop. The two-pointer variant shows deeper optimization skills by eliminating extra memory. Starting with the stack approach and then mentioning the in-place optimization is a strong interview strategy.
Approach 1: Stack-Based Approach
Use a stack data structure to efficiently remove adjacent duplicates. Traverse through the string, and for each character, check the top of the stack. If the top of the stack is equal to the current character, pop the stack. Otherwise, push the current character onto the stack. Finally, reconstruct the string from the stack.
def remove_duplicates(s: str) -> str:
stack = []
for char in s:
if stack and stack[-1] == char:
stack.pop() # Remove last character
else:
stack.append(char) # Add current character
return ''.join(stack)
print(remove_duplicates("abbaca"))public class RemoveDuplicates {
public static String removeDuplicates(String s) {
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
int length = stack.length();
if (length > 0 && stack.charAt(length - 1) == c) {
stack.deleteCharAt(length - 1); // Remove last character
} else {
stack.append(c); // Add current character
}
}
return stack.toString();
}
public static void main(String[] args) {
System.out.println(removeDuplicates("abbaca"));
}
}#include <iostream>
#include <string>
std::string removeDuplicates(const std::string& s) {
std::string stack;
for (char c : s) {
if (!stack.empty() && stack.back() == c) {
stack.pop_back(); // Remove last character
} else {
stack.push_back(c); // Add current character
}
}
return stack;
}
int main() {
std::string s = "abbaca";
std::cout << removeDuplicates(s) << std::endl;
return 0;
}function removeDuplicates(s) {
const stack = [];
for (let char of s) {
if (stack.length && stack[stack.length - 1] === char) {
stack.pop(); // Remove last character
} else {
stack.push(char); // Add current character
}
}
return stack.join('');
}
console.log(removeDuplicates("abbaca"));#include <stdio.h>
#include <string.h>
char* removeDuplicates(char* s) {
int len = strlen(s);
char* stack = (char*)malloc(len + 1);
int top = -1;
for (int i = 0; i < len; i++) {
if (top >= 0 && stack[top] == s[i]) {
top--; // Pop the stack
} else {
stack[++top] = s[i]; // Push to the stack
}
}
stack[top + 1] = '\0';
return stack;
}
int main() {
char s[] = "abbaca";
printf("%s\n", removeDuplicates(s));
return 0;
}using System;
using System.Text;
class RemoveDuplicates {
public static string RemoveDuplicatesFromString(string s) {
var stack = new StringBuilder();
foreach (char c in s) {
if (stack.Length > 0 && stack[^1] == c) {
stack.Length--; // Remove last character
} else {
stack.Append(c); // Add current character
}
}
return stack.ToString();
}
static void Main() {
Console.WriteLine(RemoveDuplicatesFromString("abbaca"));
}
}The solution uses a list as a stack to manage characters. It appends to the list, now simulating push operations, and pops the last element if an adjacent duplicate is found.
Time Complexity: O(n), as we process each character once.
Space Complexity: O(n), because of additional storage required for the stack.
Approach 2: Two-Pointer Approach
This approach also simulates stack behavior but uses a two-pointer technique on the same string to efficiently manage space without using additional data structures. It leverages the properties of strings and index manipulation to override adjacent duplicates.
def remove_duplicates_two_pointers(s: str) -> str:
arr = list(s)
i = 0
for j in range(len(arr)):
arr[i] = arr[j]
if i > 0 and arr[i] == arr[i - 1]:
i -= 2
i += 1
return ''.join(arr[:i])
print(remove_duplicates_two_pointers("abbaca"))public class RemoveDuplicatesTwoPointers {
public static String removeDuplicates(String s) {
char[] arr = s.toCharArray();
int i = 0;
for (int j = 0; j < arr.length; j++, i++) {
arr[i] = arr[j];
if (i > 0 && arr[i] == arr[i - 1]) {
i -= 2;
}
}
return new String(arr, 0, i);
}
public static void main(String[] args) {
System.out.println(removeDuplicates("abbaca"));
}
}#include <iostream>
#include <string>
std::string removeDuplicatesTwoPointers(std::string s) {
int i = 0;
for (int j = 0; j < s.size(); j++, i++) {
s[i] = s[j];
if (i > 0 && s[i] == s[i - 1])
i -= 2;
}
return s.substr(0, i);
}
int main() {
std::string s = "abbaca";
std::cout << removeDuplicatesTwoPointers(s) << std::endl;
return 0;
}function removeDuplicatesTwoPointers(s) {
let arr = s.split('');
let i = 0;
for (let j = 0; j < arr.length; j++) {
arr[i] = arr[j];
if (i > 0 && arr[i] === arr[i - 1]) {
i -= 2;
}
i++;
}
return arr.slice(0, i).join('');
}
console.log(removeDuplicatesTwoPointers("abbaca"));#include <stdio.h>
#include <string.h>
char* removeDuplicatesTwoPointers(char* s) {
int i = 0, n = strlen(s);
for (int j = 0; j < n; j++, i++) {
s[i] = s[j];
if (i > 0 && s[i] == s[i - 1])
i -= 2;
}
s[i] = '\0';
return s;
}
int main() {
char s[] = "abbaca";
printf("%s\n", removeDuplicatesTwoPointers(s));
return 0;
}using System;
class RemoveDuplicatesTwoPointers {
public static string RemoveDuplicates(string s) {
char[] arr = s.ToCharArray();
int i = 0;
for (int j = 0; j < arr.Length; j++, i++) {
arr[i] = arr[j];
if (i > 0 && arr[i] == arr[i - 1]) {
i -= 2;
}
}
return new String(arr, 0, i);
}
static void Main() {
Console.WriteLine(RemoveDuplicates("abbaca"));
}
}The Python version uses a list to represent the string for direct modifications. The `i` pointer maintains the stack-like section of unique characters, and `j` runs through each character in the string. The index `i` is updated to simulate stack pops when duplicates are present.
Time Complexity: O(n), single pass is sufficient.
Space Complexity: O(1), operating directly on input as list (but technically uses an auxiliary space in the conversion).
Approach 3: Default Approach
func removeDuplicates(s string) string {
stk := []rune{}
for _, c := range s {
if len(stk) > 0 && stk[len(stk)-1] == c {
stk = stk[:len(stk)-1]
} else {
stk = append(stk, c)
}
}
return string(stk)
}impl Solution {
pub fn remove_duplicates(s: String) -> String {
let mut stack = Vec::new();
for c in s.chars() {
if !stack.is_empty() && *stack.last().unwrap() == c {
stack.pop();
} else {
stack.push(c);
}
}
stack.into_iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n), as we process each character once. |
| Two-Pointer Approach | Time Complexity: O(n), single pass is sufficient. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Approach | O(n) | O(n) | Best general solution. Clear logic and commonly expected in interviews. |
| Two-Pointer (In-place Stack Simulation) | O(n) | O(1) | When minimizing extra memory. Uses the input array as a stack buffer. |
Frequently asked questions
Is Remove All Adjacent Duplicates In String easy or hard?
LeetCode classifies this problem as Easy with an acceptance rate around 70%+. The logic is simple once you recognize the stack pattern. The main challenge for beginners is realizing that removing pairs can trigger new adjacent duplicates.
Remove All Adjacent Duplicates In String Python/Java solution
In Python or Java, iterate through the string and maintain a stack (list or StringBuilder). Compare the current character with the last stored character. If they match, remove the last element; otherwise append the new character. This produces the final string in O(n) time.
How to solve Remove All Adjacent Duplicates In String in O(n)?
Use a stack or simulate one with two pointers. Traverse the string and compare each character with the last inserted character in the result. If they match, remove the previous character; otherwise append the new character. Because each character participates in at most one push and one pop, the algorithm runs in O(n) time.
What is the best approach for Remove All Adjacent Duplicates In String?
The stack-based approach is the most common and intuitive solution. Iterate through the string and push characters onto a stack. If the current character matches the stack's top element, pop it instead of pushing. Each character is processed once, resulting in O(n) time and O(n) space complexity.
Is Remove All Adjacent Duplicates In String asked at Google/Amazon/Meta?
String and stack problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variations include removing k adjacent duplicates or repeatedly collapsing groups of characters. Interviewers use it to test stack reasoning and in-place string manipulation.
What data structure is used in Remove All Adjacent Duplicates In String?
The primary data structure is a stack. It tracks the current valid sequence of characters while scanning the string. Some optimized implementations avoid an explicit stack and instead simulate it using a character array with two pointers.
What is the time complexity of Remove All Adjacent Duplicates In String?
The optimal solutions run in O(n) time, where n is the length of the string. Each character is pushed and popped at most once in the stack approach. The two-pointer method also scans the string once, so the total processing time remains linear.