Problem Statement:
Given a string, remove all the consecutive duplicates
Example
Input : aaaaabbbbbb Output : ab
Solution
Solution is very simple.
If the string is empty return.
else, compare the adjacent character of the string. If they are same then shift the character one to the left, call recursion on string s.
If not same, call the recursion from the next character s+1
Time complexity will be O(n^2)
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> using namespace std; void remove_duplicates(char* S) { // if string is empty, return if (S[0] == '\0') return; // check if adjacent characters are same if (S[0] == S[1]) { // Shift character by one to left int i = 0; while (S[i] != '\0') { S[i] = S[i + 1]; i++; } // Check on updated S remove_duplicates(S); } // If the adjacent characters are not same check from S+1 string remove_duplicates(S + 1); } int main() { char s[] = "hellooo"; remove_duplicates(s); cout << s << endl; }
Output:
helo