Code: Maximum Length of a Concatenated String with Unique Characters using Recursion | DSA in C++ - Software Development PDF Download

Here's a C++ code that uses recursion to find the maximum length of a concatenated string with unique characters:

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

int maxLengthUtil(vector<string>& arr, string curr, int index) {

    if (index == arr.size()) {

        // Base case: all strings have been processed

        // Check if the current string has unique characters

        if (unordered_set<char>(curr.begin(), curr.end()).size() == curr.length())

            return curr.length();

        else

            return 0;

    }

    // Exclude the current string

    int exclude = maxLengthUtil(arr, curr, index + 1);

    // Include the current string if it doesn't have duplicate characters

    if (unordered_set<char>(curr.begin(), curr.end()).size() == curr.length())

        curr += arr[index];

    int include = maxLengthUtil(arr, curr, index + 1);

    // Return the maximum length obtained by excluding or including the current string

    return max(exclude, include);

}

int maxLength(vector<string>& arr) {

    string curr = "";

    int index = 0;

    return maxLengthUtil(arr, curr, index);

}

int main() {

    vector<string> arr = {"un", "iq", "ue"};

    int maxLen = maxLength(arr);

    cout << "Maximum length of a concatenated string with unique characters: " << maxLen << endl;

    return 0;

}

Output:

Maximum length of a concatenated string with unique characters: 4

Explanation:

• The 'maxLengthUtil' function is a recursive helper function that takes three parameters: arr (a reference to the vector of strings), 'curr' (a string that stores the current concatenated string), and 'index' (an integer indicating the current index in the vector).
• In the base case, when index equals the size of the vector, it means all strings have been processed. We check if the 'curr' string has unique characters by converting it into an unordered set of characters and comparing the size of the set with the length of the string. If they are equal, we return the length of the string; otherwise, we return 0.
• In the recursive case, we have two options: either include or exclude the current string. We start by excluding the current string by making a recursive call to 'maxLengthUtil' with the same 'curr' and incrementing the 'index' by 1.
• Next, we check if the current string can be included. To do this, we check if the size of the unordered set of characters in 'curr' is equal to the length of 'curr'. If they are equal, it means there are no duplicate characters, and we can safely concatenate the current string from the vector to 'curr'.
• We make a recursive call to maxLengthUtil by passing the updated 'curr' and 'index + 1'.
• Finally, we return the maximum length obtained by either excluding or including the current string using the 'max' function.
• The 'maxLength' function serves as a wrapper function that initializes the 'curr' string as an empty string and the 'index' as 0. It calls the 'maxLengthUtil' function and returns the result.
• In the 'main' function, we create a vector of strings 'arr' containing the input strings: '{"un", "iq", "ue"}.
• We call the 'maxLength' function with 'arr' and store the result in 'maxLen'.
• Finally, we output the maximum length of the concatenated string with unique characters.