xeno3112's blog

By xeno3112, history, 4 years ago, In English

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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For a string ababa...abaaba...ababa that will take $$$O(n^2)$$$.