Following Approach can be Followed to Remove Duplicates in O(N) Time:
-
Using Hash Set:
- Iterate through the array.
- For each element, check if it exists in the hash set.
- If it doesn't exist, add it to the hash set and output it as a non-duplicate.
- If it exists, skip it as it's a duplicate.
-
Using Sorting:
- Sort the array.
- Iterate through the sorted array.
- Compare adjacent elements.
- Output only unique elements by skipping duplicates. Sorting takes O(N log N) time, but the removal step takes O(N) time.
-
Using Bit Manipulation:
- Assuming elements are integers within a specific range.
- Initialize a bit vector of size equal to the range of elements, initially set to 0.
- Iterate through the array.
- For each element, set the corresponding bit in the bit vector.
- Output only those elements whose corresponding bit is not set, indicating uniqueness. This approach requires additional memory but ensures O(N) time complexity.
Approach 1: Recursion
One obvious way that comes to mind is to remove adjacent duplicates recursively in the string till there are no duplicates left (see Recursion).
Implementation
C++
/*
Time Complexity: O(N2);
Space Complexity: O(N);
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
string removeDuplicates(string S) {
if(S.size()<2)
return S;
for(int i=0; i<S.size()-1; i++)
{
if(S[i]==S[i+1])
{
S.erase(i,2);
return removeDuplicates(S);
}
}
return S;
}
int main()
{
string s="abbaca";
cout<<removeDuplicates(s);
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output:
ca
Complexity Analysis
Time Complexity: O(N2)
Since it might require (N+1)N/2 passes in the worst case where N is the length of an input string.
Space Complexity: O(N)
Since N recursive calls can happen.
Approach 2: Using Stack
A stack can be used to overcome this problem. We can add all of the characters to the stack one by one. While adding one element to the stack, we check the top of the stack; if it is equal to our current character (i.e., two adjacent characters are the same), we pop that element and do not add our current character to the stack. As a result, we may ignore all of the neighboring characters.
Finally, we must reverse the string since they are returned in reverse order when we pop characters off the stack.
Consider the below image on string “abbaca” to get a better understanding.
Implementation
C++
/*
Time Complexity : O(N);
Space Complexity : O(N);
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
string removeDuplicates(string s) {
stack<char>ans;
for(int i = 0; i < s.size(); i++){
if(ans.empty()) ans.push(s[i]);
else if(ans.top() == s[i]) ans.pop();
else ans.push(s[i]);
}
string res;
while(!ans.empty()){
res.push_back(ans.top());
ans.pop();
}
reverse(res.begin(), res.end());
return res;
}
int main()
{
string s="abbaca";
cout<<removeDuplicates(s);
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output:
ca
Complexity Analysis
Time Complexity: O(N)
Since we are traversing the whole string.
Space Complexity: O(N)
Since we are using a stack to store characters of the string which can in the worst case store all the characters of the string.
Frequently Asked Questions
Although the Time and Space Complexity of both the Recursive Approach and Stack Approach is the same, which one will you prefer and why?
I will prefer to use a stack-based approach because the recursive method uses stack memory, and in the case of large inputs, it can give Runtime Error.
What is the time complexity of push and pop operations in a stack?
For both push and pop operations, the time complexity is O(1).
How do I remove all duplicates from a string?
To remove duplicates from a string, you can use a hash set or a similar data structure to store unique characters while iterating through the string. Then, reconstruct the string without duplicates.
How do you get rid of adjacent duplicates?
To eliminate adjacent duplicates, iterate through the string while comparing each character with the next one. If they are the same, skip the current character. Concatenate the characters that are not skipped to form the resulting string.
Conclusion
In this blog, we discussed the Remove all Adjacent Duplicates problem along with a couple of approaches to solving it utilising the concepts of stacks and recursion.
Recommended Problems
To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and some more Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Coding!!