This is the function I used for solving “removing duplicate elements from a string”. I am unable to figure out its time complexity. What is its time complexity? https://practice.geeksforgeeks.org/problems/recursively-remove-all-adjacent-duplicates/0
inline string removedup(string s){
int n = s.length();
if(n == 1)
return s;
int i = 1;
string str;
if(s[0] != s[1])
str.push_back(s[0]);
while(i < n){
if(s[i] == s[i - 1]);
else if(i < n-1 and s[i] == s[i+1]);
else
str.push_back(s[i]);
i++;
}
if(str.length() == 0)
return str;
if(str.length() != n)
return removedup(str);
return str;
}
For a string
ababa...abaaba...ababa
that will take $$$O(n^2)$$$.