Last Updated: 28 Jul, 2020
Remove Consecutive Duplicates From String
Moderate
Asked in companies
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.
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
Approaches
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.
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.
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].