Problem Statement

Write a program that removes duplicate characters from a given string using recursion.

Problem Understanding

To solve this problem recursively, we need to understand that removing duplicates involves iterating through the string and removing any duplicates occurrences of each character. Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when the length of the string becomes 0 or 1, indicating that there are no duplicates to remove.

Solution in C++

#include <iostream>
#include <string>

// Function to remove duplicates from a string
std::string removeDuplicates(const std::string& str, int index = 0) {
    // Base case: If the index exceeds or equals the length of the string
    if (index >= str.length()) {
        return "";
    }
    
    // Remove duplicates from the substring starting from the next character
    std::string next = removeDuplicates(str, index + 1);
    
    // If the next substring already contains the current character, skip it
    if (next.find(str[index]) != std::string::npos) {
        return next;
    }
    
    // Otherwise, append the current character to the next substring
    return str[index] + next;
}

int main() {
    std::string str;

    // Prompt the user to enter a string
    std::cout << "Enter a string: ";
    std::getline(std::cin, str);

    // Remove duplicates from the string
    std::string result = removeDuplicates(str);

    // Print the resulting string without duplicates
    std::cout << "String without duplicates: " << result << std::endl;

    return 0;
}