Question

Write a C++ program that uses a de-duplication function that iteratively sanitizes (removes) all consecutive duplicates in a C++ string. Consecutive duplicates are a pair of duplicate English alphabets sitting next to each other in the input string. Example: "AA", "KK", etc., are all consecutive duplicates. This function will internally run as many iterations as needed to remove all consecutive duplicates until there is either no consecutive duplicates left, or the string becomes empty (in which the function returns "Empty" back to the user):

string deduplicate(string input)

Your main() may look like the following, or anything you prefer to put in it as it is not graded:

int main() {
  cout << deduplicate("AABB"); // should output "Empty"
  cout << deduplicate("A"); // "A"
  cout << deduplicate("ABBA"); // should output "Empty"
  cout << deduplicate("AAA"); // "A"
  cout << deduplicate("AKA"); // "AKA" because there is no consecutive pair.
  return 0;
}

-----------------------------------------------------------

Examples:

• "KCCK" -> first iteration results in "KK" by removing "CC" as consecutive duplicates -> second iteration starts with "KK" as consecutive duplicates hence removed. Function returns "Empty".
• "ZZZ" -> first iteration results in "Z" by removing the first "ZZ". There is nothing to be removed after that. Function returns "Z".
• "KKCCD" -> first iteration removes "KK" resulting in "CCD" -> second iteration removes "CC" resulting in "D". There is nothing left to be removed. Function return "D".

-----------------------------------------------------------

Constraints/Assumptions:

• Input string consists of only uppercase English alphabets, "A" - "Z".
• Input string consists of at least 1 English alphabet.
• Input string consists of at most 100 alphabets.
• Function returns the non-reducible string.
• If the reduced string is empty, function returns the string "Empty".

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

#include<iostream>

using namespace std;

//required method

string deduplicate(string input){

                //a flag denoting if duplicate is found, setting to true initially

                bool duplicates=true;

                //looping as long as duplicates is true

                while(duplicates){

                                //at the start of each loop, initially setting duplicates to false

                                duplicates=false;

                                //a string to store the updated text

                                string updated="";

                                //looping through each index in input string

                                for(int i=0;i<input.length();i++){

                                               //checking if next index is valid, and characters at indices i and i+1 are same

                                               if((i+1)<input.length() && input[i]==input[i+1]){

                                                               //setting duplicates to true

                                                               duplicates=true;

                                                               //advancing i, skipping next character

                                                               i++;                                       

                                               }else{

                                                               //otherwise simply appending current character to updated

                                                               updated+=input[i];

                                               }

                                }

                                //at the end of each iteration of outer loop, setting updated as input (for next loop)

                                input=updated;

                }

                //at the very end, if input is empty, returning "Empty", else returning input

                if(input==""){

                                return "Empty";

                }else{

                                return input;

                }

}

int main(){

                //testing

                cout << deduplicate("AABB")<<endl; // should output "Empty"

                cout << deduplicate("A")<<endl;// "A"

                cout << deduplicate("ABBA")<<endl; // should output "Empty"

                cout << deduplicate("AAA")<<endl; // "A"

                cout << deduplicate("AKA")<<endl; // "AKA" because there is no consecutive pair.

                cout << deduplicate("ZZZ")<<endl;// "Z"

                cout << deduplicate("KKCCD")<<endl;// "D"

                return 0;

}

/*OUTPUT*/

Empty

A

Empty

A

AKA

Z

D