Remove Consecutive Duplicates From String
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

Question

Remove Consecutive Duplicates From String

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

Accepted Answer

The task is to remove consecutive duplicate characters from a given string and return the new string.

Iterate through the characters of the string
Compare each character with the next character
If they are the same, skip the next character
If they are different, append the current character to the new string

Accepted Answer

First I explained to him the brute force with pseudo code.
-> Recursively calling the same method, until the compression is possible.
-> Complexity : O(n^2)

Also explained to him an optimized solution using stack, complexity is O(N)

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n)Explanation:

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).

Accepted Answer

Two Pointer Approach

Let our input string be

str =

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.

Space Complexity: O(n)Explanation:

O(N), Where N is the length of the string.

Since a new string has been formed which will take O(N) space. So overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the size of the string

Traversing the string once takes O(N) time.

Accepted Answer

Space Optimsed Two Pointer Approach

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].

Space Complexity: O(1)Explanation:

O(1).

Since the changes are made in the given input string only, therefore constant space is being used. So overall, space complexity is O(1).

Time Complexity: O(n)Explanation:

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

Since we are traversing over the string ‘STR’ which will take O(N) time. So overall time complexity will be O(N).

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 :

Input Format :

Output Format :

Note :

Constraints :

Top Meesho SDE-2 interview questions & answers

Popular interview questions of SDE-2