Last Updated: 25 Nov, 2020
Remove Consecutive Duplicates
Easy
Asked in companies
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.
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.
Approaches
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.