Remove Consecutive Duplicates

Easy
0/40
profile
Contributed by
84 upvotes
Asked in companies
OlaInfo Edge India (Naukri.com)Tata Consultancy Services (TCS)

Problem statement

You are given a string ‘str’ of size ‘N’. Your task is to remove consecutive duplicates from this string recursively.

For example:

If the input string is ‘str’ = ”aazbbby”, then your output will be “azby”.
Note that we are just removing adjacent duplicates.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the size of the given string.

The second line of each test case contains a string of size ‘N’.

Output Format:

For each test case, print the new string that doesn’t have consecutive duplicates.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 5
1 <= N <= 1000

Where ‘T’ is the number of test cases, ‘N’  is the length of the given string, and the given string contains only lowercase English letters.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1:

2
7
aazbbby
6
aabbcb

Sample Output 1:

azby
abcb

Explanation of Sample Input 1:

Test Case 1:

Given ‘str' = ”aazbbby”
After removing adjacent duplicates string will be “azby”

Test Case 2:

Given ‘str’ = “aabbcb”
After removing adjacent duplicates string will be “abcb”

Sample Input 2:

2
5
abcde
5
aaaaa

Sample Output 2:

abcde
a

Explanation of Sample Input 2:

Test Case 1:

Given ‘str' = ”abcde”
There are no duplicates in the input string so the final string will be “abcde” 

Test Case 2:

Given ‘str’ = “aaaaa”
After removing adjacent duplicates string will be “a”
Hint

Either we remove a character or it will remain in the final string.

Approaches (1)
Recursion

The idea is here to use recursion as mentioned in the problem statement. For each character either it will be included in the answer or not, how to decide this at each point?

We will compare the last and 2nd last character of the string each time if they are equal we will remove the last and call recursion for the remaining string, if they both are not equal then we will append the last character into our final string and call recursion for the remaining string.

 

Algorithm:

 

  • Check for the base case if the size of the string is less than 2 then return the string itself.
  • Compare the last and 2nd last character of the string if
  • Both are equal remove last and call recursion for remaining string
  • Both are not equal call recursion for the remaining part and add the last character to the end.
  • We are returning at each step as a recursive call.

 

Time Complexity

O(N), where N is the total number of characters in the string.


At each step in recursion, we will decrease the length of the string by one, so for a string of ‘N’ length we need to call recursion ‘N’ times. So time complexity will be O(N).

Space Complexity

O(N), where N is the total number of characters in the string.

 

As we are not taking any extra space in the function but calling recursion ‘N’ time will add space complexity O(N) for the recursion stack.

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