Q2. Ramu has an array of strings. He want to find a string s such that it is a concatenation of sub-sequence of given array and have unique characters. A sub-sequence of an array is a set of elements that can be obtained by deleting zero or more elements from the array and keeping the order same. Write a program to print the maximum possible length of s.

Question Link - Click Here to Solve This Problem

Intuition Behind the Algorithm

The underlying approach is to use recursion to explore all possible combinations of subsequences. Each recursive step decides whether to include or exclude the current string from the array in building the unique string s. The key is to ensure that at each step, the resultant string maintains its uniqueness of characters.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Recursive function to find the maximum length of a unique character string
int Fun(vector<string> v, int i, string s) {
    // Base case: When all strings have been considered
    if (i == v.size()) {
        // If length of the string s is greater than 26, it can't be unique
        if (s.length() > 26)
            return 0;

        // Frequency array to check for unique characters in s
        int freq[26] = {0};
        for (int k = 0; k < s.length(); k++) {
            // If character is repeated, return 0
            if (freq[s[k] - 'a'] == 1)
                return 0;
            freq[s[k] - 'a']++;
        }
        // Return the length of s if all characters are unique
        return s.length();
    }

    // Variables to store results of including or excluding the current string
    int op1, op2;
    op1 = op2 = INT_MIN;

    // Include the ith string if it doesn't make the total length exceed 26
    if (s.length() + v[i].length() <= 26) {
        op1 = Fun(v, i + 1, s + v[i]);
    }

    // Exclude the ith string and move to the next index
    op2 = Fun(v, i + 1, s);

    // Return the maximum of including or excluding the ith string
    return max(op1, op2);
}

// Function to start the process and return the result
int UniqueString(vector<string>& v) {
    string s = "";
    return Fun(v, 0, s);
}

int main() {
    vector<string> v;
    int n;
    cin >> n;

    // Reading the array of strings
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        v.push_back(s);
    }

    // Finding and printing the maximum length of unique string
    cout << UniqueString(v) << endl;

    return 0;
}

Code Walkthrough

• Recursive Function Fun: This function takes the vector of strings v, the current index i, and the currently formed string s. It returns the maximum length of a unique character string formed so far.

• Base Case: If i equals the size of v, it checks if s has unique characters and returns its length if unique; otherwise, returns 0. Frequency Array: It ensures that each character in s appears only once.

• Recursive Calls: Two scenarios are considered:

  • Including the current string: Concatenate v[i] to s and recursively call Fun with i+1.

  • Excluding the current string: Move to the next index without altering s.

• Main Function UniqueString: Initiates the recursive process and returns the result.

Time and Space Complexity Analysis

• Time Complexity: O(2^n), where n is the number of strings in the array. In the worst case, the algorithm explores two possibilities (include or exclude) for each string.
• Space Complexity: O(n), mainly due to the recursive call stack. The depth of recursion can go up to n, and additional space for the frequency array and temporary strings is constant.

Key Points of the Algorithm

• Recursion and Backtracking: The core of the algorithm lies in exploring all possible unique string formations using recursion.
• Optimization Checks: The function checks if the total length exceeds 26 (the total number of lowercase alphabets) to prune unnecessary recursive calls.
• Uniqueness Check: The frequency array is crucial for ensuring the uniqueness of characters in the formed string.

Conclusion and Further Optimizations

The provided solution effectively solves the problem using a backtracking approach. However, there are possibilities for optimization:

• Memoization: To avoid re-computation, storing results of subproblems can significantly improve performance.
• Bitmasking: Instead of using a frequency array, a bitmask can represent the presence of characters, thus reducing space complexity and potentially speeding up the checks for uniqueness.