Problem

You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.

Return the maximum possible length of s.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Examples

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.

Solution

Method 1 - Backtracking

Here is the approach:

  1. Backtracking: We will use backtracking to explore all possible subsequences of the given array.
  2. Unique Characters: For each subsequence, we will check if the concatenated string has all unique characters.
  3. Max Length: We will keep track of the maximum length of such valid strings.

Code

Java
class Solution {
    public int maxLength(List<String> arr) {
        return helper(arr, 0, "");
    }

    private int helper(List<String> arr, int start, String current) {
        if (!isUnique(current)) return 0;
        int ans = current.length();
        for (int i = start; i < arr.size(); i++) {
            ans = Math.max(ans, helper(arr, i + 1, current + arr.get(i)));
        }
        return ans;
    }

    private boolean isUnique(String s) {
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (set.contains(c)) return false;
            set.add(c);
        }
        return true;
    }
}
Python
class Solution:
    def maxLength(self, arr: List[str]) -> int:
        return self.helper(arr, 0, "")
    
    def helper(self, arr: List[str], start: int, current: str) -> int:
        if not self.is_unique(current):
            return 0
        ans = len(current)
        for i in range(start, len(arr)):
            ans = max(ans, self.helper(arr, i + 1, current + arr[i]))
        return ans
    
    def is_unique(self, s: str) -> bool:
        return len(s) == len(set(s))

Complexity

  • ⏰ Time complexity: O(2^n * n), where n is the number of strings in the array. This is because we are generating all possible subsequences (which is 2^n) and for each subsequence, we are checking if the characters are unique (taking O(n) time in the worst case).
  • 🧺 Space complexity: O(n), used by the recursion stack and to store unique characters for each subsequence.