Last Updated on March 30, 2022 by Ria Pathak
Concepts Used
Stack
Difficulty Level
Easy
Problem Statement :
Given a string str of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on str until we no longer can.
See original problem statement here
Example:
Input:
bccbdb
Output:
db
Explanation:
In "bccbdb"
we can remove "cc" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "bbdb", of which only "bb" is possible, so the final string is "db".
We push 'b' to the stack,then 'c' .
Now when we reach index 2 i.e. 'c',we pop from stack as the current element matches the top of stack.Solving Approach:
BRUTE FORCE:
-
Recursively remove all adjacent duplicates in the string till no duplicates is left in the string.
-
Can we make it any better??
Using stack:
-
This is the standard stack problem.Let’s see how stack works here.
-
Iterate through the string from left to right,if stack is empty put the current character onto the stack.
-
Else check if the top of the stack equals the current element then pop the top element from the stack, if not push the current element.
-
In this way we are exploiting the LIFO property of the stack.Now add the contents of the stack onto new string and reverse it to preserve the order.Below solution explains it better.
Solutions:
#include <stdio.h>
#define ll long long
void removeDuplicates(char s[],int l) {
char st[l];int top=-1;
for(int i=0;i<l;i++)
{
if(top==-1) st[++top]=(s[i]);
else
{
if(st[top]==s[i])
{
top--;
}
else
{
st[++top]=(s[i]);
}
}
}
char ans[l];int j=0;
while(top>=0)
{
ans[j++]=(st[top]);
top--;
}
for(int i=j-1;j>=0;j--)
printf("%c",ans[i]);
printf("\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
char s[20004];
scanf("%s",s);
removeDuplicates( s,strlen(s));
}
return 0;
}
#define ll long long
#include <bits/stdc++.h>
using namespace std;
string removeDuplicates(string s) {
stack<char>st;
for(int i=0;i<s.length();i++)
{
if(st.empty()) st.push(s[i]);
else
{
if(st.top()==s[i])
{
st.pop();
}
else
{
st.push(s[i]);
}
}
}
string ans ="";
while(!st.empty())
{
ans.push_back(st.top());
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
s=removeDuplicates( s);
cout<<s<<endl;
}
return 0;
}
import java.io.*;
import java.util.*;
class prepbytes {
static String removeUtil(String str, char last_removed)
{
if (str.length() == 0 || str.length() == 1)
return str;
if (str.charAt(0) == str.charAt(1))
{
last_removed = str.charAt(0);
while (str.length() > 1 && str.charAt(0) == str.charAt(1))
str = str.substring(1, str.length());
str = str.substring(1, str.length());
return removeUtil(str, last_removed);
}
String rem_str = removeUtil(str.substring(1,str.length()), last_removed);
if (rem_str.length() != 0 && rem_str.charAt(0) == str.charAt(0))
{
last_removed = str.charAt(0);
return rem_str.substring(1,rem_str.length());
}
if (rem_str.length() == 0 && last_removed == str.charAt(0))
return rem_str;
return (str.charAt(0) + rem_str);
}
static String remove(String str)
{
char last_removed = '\0';
return removeUtil(str, last_removed);
}
// Driver code
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
String str= sc.nextLine();
System.out.println(remove(str));
} }}
# your code goes here def removeDuplicates(s): st = [] for i in range(len(s)): if len(st)==0: st.append(s[i]) else: if st[-1] == s[i]: st.pop() else: st.append(s[i]) ans = "" while st: ans = ans + st[-1] st.pop() ans = ans[::-1] return ans s = input() s = removeDuplicates(s) print(s)
[forminator_quiz id="1998"]
This article tried to discuss the concept of stack. Hope this blog helps you understand and solve the problem. To practice more problems on stack, Recursion you can check out MYCODE | Competitive Programming.