Remove all adjacent duplicates

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:

  1. Recursively remove all adjacent duplicates in the string till no duplicates is left in the string.

  2. Can we make it any better using fundamentals of data structures in c++??

Using stack:

  1. This is the standard stack problem.Let’s see how stack works here.

  2. Iterate through the string from left to right,if stack is empty put the current character onto the stack.

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

  4. 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));
     } }}
Previous post Get minimum element from stack
Next post Sort stack

Leave a Reply

Your email address will not be published. Required fields are marked *