Remove Consecutive Duplicates From String

Moderate
0/80
Average time to solve is 22m
profile
Contributed by
30 upvotes
Asked in companies
AmazonMeeshoIntuit

Problem statement

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.


Note : 
You don't have to print anything, it has already been taken care of. Just implement the given function.
Detailed explanation ( Input/output format, Notes, Images )
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.
Constraints : 
1 <= |S| <= 10^5

Where |S| represents the length of the string.

Time limit: 1 sec
Sample Input 1 :
aabccba
Sample Output 1 :
abcba
Explanation of Sample Output 1 :
The string basically is a concatenation of [aa][b][cc][b][a] without considering the brackets. From each segment we need to choose only 1 character as all the characters are duplicates, therefore the final answer is [a][b][c][b][a] = abcba
Sample Input 2 :
xxxyyyzwwzzz
Sample Output 2 :
xyzwz
Explanation of Sample Output 2 :
The string basically is a concatenation of [xxx][yyy][z][ww][zzz]. After choosing 1 character from each segment our final answer is [x][y][z][w][z] = xyzwz
Hint

Traverse the string from the right and store the characters in a stack.

Approaches (3)
Stack - Based Approach

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.
Time Complexity

O(N), where ‘N’ is the length of the string ‘STR'.

 

Since we are traversing over the string ‘STR’ and performing push operation on stack st which will take O(N) time. Again traversing over the stack st of length at max N and performing a pop operation which will take O(N) time. So overall time complexity will be O(N). 

Space Complexity

O(N), where ‘N’ is the length of the string ‘STR’.


 

Since the stack is used to store the characters of the string which will take O(N) space. So overall, space complexity is O(N).

Code Solution
(100% EXP penalty)
Remove Consecutive Duplicates From String
Full screen
Console