Remove Consecutive Duplicates From String

PROBLEM STATEMENT

For a given string, "aaaAAbbcccbd"

The new string formed after removing the consecutive duplicates characters will be, "aAbcbd".

The first and the only line of input contains a string 'STR' with no space in between the characters.

Print the final string after removing all the consecutive duplicates.

You don't have to print anything, it has already been taken care of. Just implement the given function.

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.

Approach 2

Let our input string be

str = <str[0], str[1], … str[n - 1]>

where str[i] denotes the i'th character of the string and n denotes the length of the string.

STEPS

Initialize an empty string, ans, that will be used to store the modified string.
Push the ‘0’th character in the ans as it's sure that ‘0’th character is not equal to any previous character.
We will iterate through all characters of the string starting from index 1 and going till index n - 1
If for any index i, str[i] and str[i - 1] are different, we will append str[i] to ans.
Return ans.

Approach 3

Algorithm:

Create two variables ‘i’ and ‘j’ both initialized to 0.
Now run a loop till ‘j’ < length of the input string ‘STR’ and perform the following steps:
- Now keep incrementing the pointer by one ‘j’ till the ‘ith’ character is equal to the ‘jth’ character.
- Now if the ‘ith’ character is not equal to the ‘jth’ character then perform the following steps:
  - Increment ‘i’ by 1.
  - Update character at the ‘ith’ position with the character at the ‘jth’ position.
Now our final answer string will lie between index [0, i].