Remove Consecutive Duplicates From String

Posted: 28 Jul, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a string 'STR' consisting of lower and upper case characters. You need to remove the consecutive duplicates characters, and return the new string.

Example :
For a given string, "aaaAAbbcccbd"

The new string formed after removing the consecutive duplicates characters will be, "aAbcbd".
Input Format :
The first and the only line of input contains a string 'STR' with no space in between the characters.
Output Format :
Print the final string after removing all the consecutive duplicates.
Note :
You don't have to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= |S| <= 10^5

Where |S| represents the length of the string.

Time limit: 1 sec
Approach 1

Approach :

  • This is a stack-based approach where we will iterate through the string from the right side.
  • While iterating we will check if the top of the stack is not equal to the current character of the string. If so, then we will push the character into the stack. Otherwise, we will continue to move in the leftward direction.
  • Finally, we will form the answer by concatenating the top elements of the stack.

 

Algorithm: 

  • Create a stack st.
  • Push the last character of the string into the stack.
  • Now iterate through the string from the second last character till the first character and or each character do the following operations:
    • If the current character of the string ‘STR’ is not equal to the top element of the stack then we will push the current character of the string into the stack.
    • Otherwise, continue iterating over the string.
Try Problem