How to delete duplicates in a string using recursion?

Question

I'm working on a function that uses recursion in order to delete duplicate characters in a string. Problem is, I'm not sure how to keep passing a string along in order to keep comparing adjacent characters without cutting the string somehow. Here's what I have so far:

string stringClean(const string& str)
{
   string s1 = str;

   if (/*first char == next char*/)
      s1.at(/*first char*/) = "";
      return stringClean(s1);
   else 
      return s1;
}

As an example, stringClean("yyzzza") should return "yza". Any tips on how I should proceed?

stringClean("abbbcdd") → "abcd" stringClean("Hello") → "Helo" — JURO312
– JURO312, Commented Nov 18, 2017 at 4:45
if (str[0]==str[1]) return str[0]+stringClean(str.substr(2)); else return str[0]+stringClean(str.substr(1)); Terminating condition is left as an exercise for the reader. — Igor Tandetnik
– Igor Tandetnik, Commented Nov 18, 2017 at 4:51
The problem is not a good candidate for a recursive solution. Is this a homework problem? In any case, you need to be more specific than asking for "any tips". As asked, the question in effect calls for a tutorial on how to write recursive functions generally. Read stackoverflow.com/help/asking. Pay particular attention to #5 - MCVE. Then post a MCVE that shows more effort. — Jive Dadson
– Jive Dadson, Commented Nov 18, 2017 at 4:57

CMPS · Accepted Answer · 2017-11-18 05:29:18Z

1

C++

Here's what I just thought about

#include <iostream>
#include <string>

std::string rec(std::string &word, int index);
std::string rec(std::string word) {
    if(word.length() <= 1) {
         return word;
    }
    return word[0] + rec(word, 1);
}

std::string rec(std::string &word, int index) {
   if(index == word.length()) {
       return "";
   }
   return (word[index] != word[index-1] ? std::string(1, word[index]) : "") + rec(word, index+1); 
}

int main() {
    std::cout << rec("aaabbbbcccddd") << std::endl;
}

For one line recursion lovers:

std::string rec(std::string &word, int index) {
   return index == word.length() ? "" : (word[index] != word[index-1] ? std::string(1, word[index]) : "") + rec(word, index+1); 
}

edited Nov 18, 2017 at 5:29

answered Nov 18, 2017 at 5:10

CMPS

7,7974 gold badges32 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user5550963 Over a year ago

What if you have abcdabcddcbadcba?

Casey · Accepted Answer · 2021-05-20 05:19:08Z

Algorithm:

Start from the leftmost character and remove duplicates at the left corner if there are any.
If the length of the string is zero or one then return the string.
Check the leftmost character in the starting substring. If it is present then
- Recur for a string of length n-1 (string without last character).
If the leftmost character is not present in the starting substring, then
- Recur for the remaining string and store the unique character.

Implementation:

#include <string>
#include <iostream>

using namespace std;

string removeDups(string s) {
    if(s.length() <= 1) return s;
    if(s.substr(0, s.length() - 1).find(s.substr(s.length() - 1, s.length())) != string::npos) {
        return removeDups(s.substr(0, s.length() - 1));
    } else {
        return removeDups(s.substr(0, s.length() - 1)) + s.substr(s.length() - 1, s.length());
    }
}


int main() {
    string s;
    cin >> s;
    cout << removeDups(s);
    
    return 0;
}

Collectives™ on Stack Overflow

How to delete duplicates in a string using recursion?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related