{"id":1994,"date":"2020-07-01T09:46:02","date_gmt":"2020-07-01T09:46:02","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1994"},"modified":"2022-03-30T22:42:47","modified_gmt":"2022-03-30T22:42:47","slug":"remove-all-adjacent-duplicates","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/remove-all-adjacent-duplicates\/","title":{"rendered":"Remove all adjacent duplicates"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Stack<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a string str of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.<\/p>\n

We repeatedly make duplicate removals on str until we no longer can.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Example:<\/h4>\n
Input:\nbccbdb\n\nOutput:\ndb\n\nExplanation:\nIn "bccbdb"\n\nwe 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".\n\nWe push 'b' to the stack,then 'c' .\n\nNow when we reach index 2 i.e. 'c',we pop from stack as the current element matches the top of stack.<\/code><\/pre>\n
Solving Approach:<\/h3>\n
BRUTE FORCE:<\/h4>\n
    \n
  1. \n
    Recursively remove all adjacent duplicates in the string till no duplicates is left in the string.<\/p>\n<\/li>\n
  2. \n
    Can we make it any better??<\/p>\n<\/li>\n<\/ol>\n
    Using stack:<\/h4>\n
      \n
    1. \n
      This is the standard stack problem.Let’s see how stack works here.<\/p>\n<\/li>\n
    2. \n
      Iterate through the string from left to right,if stack is empty put the current character onto the stack. <\/p>\n<\/li>\n
    3. \n
      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. <\/p>\n<\/li>\n
    4. \n
      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.<\/p>\n<\/li>\n<\/ol>\n
      \"\"<\/p>\n
      Solutions:<\/h3>\n\t\t\t\t\t\t