Maximum Length of a Concatenated String with Unique Characters

Explore More Solutions

Ah, the classic dilemma of trying to create the longest string possible without repeating any characters. It’s like trying to throw a party where no one wears the same outfit—impossible, right? You invite your friends, and somehow, everyone shows up in the same shirt. In the world of strings, this problem is a bit more mathematical but just as chaotic!

Problem Description

You are given an array of strings, and your task is to concatenate them into a single string such that no characters are repeated. The goal? To find the maximum length of this concatenated string. Think of it as trying to fit as many unique toppings on a pizza without repeating any—good luck with that if your friends are picky eaters!

Code Solution


class Solution {
 public:
  int maxLength(vector& arr) {
    vector masks;

    for (const string& s : arr) {
      const int mask = getMask(s);
      if (mask != -1)
        masks.push_back(mask);
    }

    return dfs(masks, 0, /*used=*/0);
  }

 private:
  int dfs(const vector& masks, int s, unsigned used) {
    int res = popcount(used);
    for (int i = s; i < masks.size(); ++i)
      if ((used & masks[i]) == 0)
        res = max(res, dfs(masks, i + 1, used | masks[i]));
    return res;
  }

  int getMask(const string& s) {
    int mask = 0;
    for (const char c : s) {
      const int i = c - 'a';
      if ((mask & (1 << i)) != 0)
        return -1;
      mask |= 1 << i;
    }
    return mask;
  }
};

Approach Explanation

The code uses a bitmasking technique to represent the characters in each string. Each string is converted into a bitmask where each bit represents whether a character is present or not. The dfs function explores all possible combinations of these masks, ensuring that no characters overlap. It’s like a game of Tetris, where you want to fit the pieces together without leaving gaps!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(2^N * N), where N is the number of strings. This is because we explore all subsets of strings.
Space Complexity	O(N), for storing the masks.

Real-World Example

Imagine you’re at a buffet with a limited number of plates, and you want to pile on as many unique dishes as possible without repeating any. You can only take one of each dish, and you want to maximize your plate's capacity. This problem is akin to that scenario—finding the optimal combination of unique strings to create the longest possible string.